Divide and Conquer

Codeforces 448C: Painting Fence

울타리를 칠해보자. 울타리는 폭이 1m이고 높이가 제각각인 널빤지들로 구성되어 있다. 울타리를 칠하기 위해 폭이 1m인 stroke를 한 번 그을 때, 가로 혹은 세로로 그을 수 있으며 stroke를 한 번 그을 때마다 길이에 상관없이 비용은 1로 동일하다. 이때 stroke를 최소 몇 번 그어야 전체 울타리를 칠할 수 있는가?

Key Point 1

가로로 칠하든 세로로 칠하든 일부만 칠하는 것은 의미가 없다.

왜냐하면 일부만 칠하나 끝까지 칠하나 비용은 같기 때문에 만약 일부만 칠한 것이 답이면, 끝까지 칠한 것은 더 칠한 것이기 때문이다.

가로도 마찬가지이다. 동일한 이유로 한 번 칠을 할 때 가능한 끝까지 칠해야 한다.

Key Point 2

가로로 stroke를 긋는다면, 이 가로 stroke는 가장 아래에 존재해야 한다.

가로 stroke 중 가장 아래에 있는 stroke를 보자. 그리고 이 stroke가 바닥으로부터 떨어져있다고 (gap이 있다고) 해보자.

그러면 이 가로 stroke가 아래서부터 올라왔을 때 최초로 가로로 그은 stroke이므로, 이 가로 stroke 아랫 부분은 세로로 칠해져 있다. 그런데 stroke를 세로로 한 번 그을 때 끝까지 그을 수 있는데, 가로로 굳이 칠할 필요가 없지 않나?

이런 경우는 정답이 될 수 없다. 따라서 가로로 획을 긋는 경우는 울타리의 가장 아래에 위치해야 한다.

Key Point 3

가로 stroke 를 긋는다면 가로 stroke들이 끝까지 쌓여있어야 한다.

여기서 끝은 전체 울타리 중 높이가 가장 낮은 널빤지의 높이만큼을 의미한다.

만약 끝까지 칠하지 않았다고 하면, 울타리에서 남은 부분들은 세로로 칠해줘야 하니까 가로로 칠하나 마나이기 때문이다.

정리

정리하자면 가로 stroke가 있을 때는 아래서부터 높이가 가장 낮은 널빤지의 높이만큼은 가로로 칠하고, 그 다음 세로로 칠해야 한다.

가로 stroke를 긋지 않는 경우: 널빤지의 개수가 정답
가로 stroke를 긋는 경우: 재귀

가로 stroke를 그으면 분리된 나머지 부분들이 생긴다. 이 부분들은 별개의 문제로 보고 divide & conquer하면 됨!

Implementation

Input

울타리를 구성하는 널빤지의 개수 n (1 <= n <= 5000)
i번째 널빤지의 높이 ai (1 <= ai <= 10^9)

모두 20억 이하의 수들이므로 int 타입으로 선언하면 된다.

Output

긋는 stroke의 최소 수. 최악의 경우 널빤지를 세로로 다 칠하면 되니까 정답은 널빤지의 개수인 5000보다 작다. 따라서 정답도 int 단위!

Complexity

D&C니까 N^2 정도로 잡고 메모리 제한은 512MB이고 5000*5000 = 25,000,000 이니까 충분함. 메모리를 많이 쓰는 식으로 구현해도 될 듯 하다..!

Code

교수님 코드입니다… minHeight로 자르고 남은 부분들을 divide할 때 배열을 복사하려 했는데, 스택이 터져서 그냥 하나의 배열로 해결했다. 이미 본 값들을 다시 보지 않기 때문에, 재귀를 돌 때마다 minHeight를 빼 주었다.

그리고 while문 돌릴 때 배열 범위 밖으로 빠져나가는지 체크 잘 해주기! 실수하기 쉽다.

#include <iostream>
#include <algorithm> // min
#define MAX 5001
using namespace std;

int a[MAX];

int solve(int start, int end) {
	int vertical, horizontal, minHeight, i, j, s, t;

	vertical = end;

	// 가로로 칠할 수 있는 만큼 칠하고 시작. 먼저 가로로 최대 얼마만큼 칠할 수 있는지 계산한다.
	minHeight = 1000000001;
	for (i = start; i <= end; i++) minHeight = min(minHeight, a[i]);
	
	// 가로로 칠하기
	horizontal = minHeight;
	for (i = start; i <= end; i++) a[i] -= minHeight;
	
	// 그럼 이제 부분이 나눠졌을 거임. 나눠진 부분을 찾아서 재귀를 돌린다.
	i = start;
	while (i <= end) {
		while (a[i] == 0) i++;
		if (i <= end) {
			s = i; // 잘라서 볼 시작과
			while (a[i] > 0 && i <= end) i++;
			t = i - 1; // 끝을 정하기
			horizontal = solve(s, t); // 시작과 끝에 대해 풀어라
		}
	}

	return min(vertical, horizontal);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, i;
	cin >> N;

	for (i = 0; i < N; i++) cin >> a[i];

	cout << solve(0, N - 1) << endl;
	return 0;
}

Codeforces 768B: Code For 1

문제
흔한 패턴의 문제.

입력으로 숫자 N이 주어진다. 리스트에서 N을 꺼내고 N/2, N % 2, N/2를 집어넣는다. 리스트의 모든 원소의 값이 0 또는 1이 될 때 까지 이 과정을 계속할 때, 리스트의 주어진 범위 내에서 1의 개수를 구해보자.

처음에 N의 범위가 0이상 2^50 미만이라 깜짝 놀랐지만, 2^50은 몇인지 가늠도 안되기에 진짜 배열에 이 값들을 집어넣는 식으로 구현하면 안된다는 것을 눈치챘다.

그리고 앞뒤로 N/2이기 때문에 한 번 계산할 때 *2해주면 되고, N % 2는 결과가 0/1이기 때문에 재귀를 돌릴 필요 없이 1일 경우에만 cnt값을 증가시키면 된다. 그리고 N/2가 0 또는 1일 될 때 까지 이 과정을 재귀로 반복하면 금방 풀 수 있을 것 같다.

근데 이렇게 풀면 전체 리스트에서 1의 개수는 금방 구할 수 있을 것 같은데, 리스트 내의 특정 범위 내에서의 1의 개수는 어떻게 구해야 하나?

교수님 설명

N의 범위로부터 유추해야 하는 중요한 포인트는 전체 sequence를 다 만들 수 없다는 것이다. 그리고 N이 주어지면 우리가 필요한 숫자는 1부터 N까지가 아닌 N/2 , N/4, N/8, N/16, .. 뿐이다. 그러므로 배열을 하나 선언해 사용될 값들에 대한 정보들만 저장해 놓는다.

N=17이라 하고 문제를 풀어보자.

문제를 풀기 위해 사용될 숫자는 17을 2로 계속 나눈 값들인 17, 8, 4, 2, 1이다. 사용될 값들을 배열에 담아보자.

Index	0	1	2	3	4
N	17	8	4	2	1
가운데 들어올 숫자(N%2)	1	0	0	0	X
N을 표현하는데 사용되는 1의 개수	17	8	4	2	1

N을 표현하는데 사용되는 1의 개수는 N/2을 표현하는데 사용되는 1의 개수 *2에 가운데가 1일 때 1을 더해주면 된다.

그럼 이제 sequence의 범위만 고려하면 된다.

만약 [l, r]이 전체 범위를 커버하는 경우에는 배열에 미리 저장해두었던 값을 그대로 리턴해주면 된다.

그렇지 않으면 몇 가지 케이스로 나눌 수 있다.

[l, r]이 중간점(N%2)을 포함하는 경우
중간점(N%2)을 포함하지 않는 경우

Case 1. 중간점을 포함하는 경우

중간점을 기준으로 left, right로 나눠 각각 재귀를 호출하면 된다.

Case 2. 중간점을 포함하지 않는 경우

재귀를 한 번만 호출한다.

범위에 중간점을 포함되는 경우 재귀를 2번 호출하는데, 너무 많이 호출하는 것은 아닐까?

그럼 범위에 중간점을 포함하는 경우가 몇 번 발생하는지 알아보자.

중간점에 의해 나눠진 두 부분이 또 그 내부의 중간점에 의해 나눠질 수 있으므로 최대 4개의 부분이 생길 수 있다.

그러나 그림에서 보다시피 1-2와 2-1는 전체 부분이다. 따라서 배열의 값을 그대로 리턴하면 되고 실제로 재귀를 부르는 부분은 최대 두 개인 것을 알 수 있다.

즉 중간점을 포함해 두 개의 부분으로 나눠지면, 그 아래 단계에서는4개로 늘어나지 않고 최대 2번까지만 호출된다는 것이다. 그래서 재귀 호출 횟수가 O(logN)이 된다.

이렇게 범위에 따라 재귀 호출 횟수가 차이나기 때문에 전 범위인지 여부를 체크하는 것이 필수적이다!