January 18, 2019 22:00

그리디 알고리즘 스터디

12월 말부터 한양대의 알고리즘 동아리 후배들을 대상으로 스터디를 진행하고 있습니다.

매주 한가지 분야에 대한 문제들을 여러개 풀어보는 방식으로 진행할 계획인데요, 1주차에는 그리디 알고리즘에 관한 문제들을 풀어보았습니다.

**<푼 문제들="">**

1. 뒤집기 (https://www.acmicpc.net/problem/1439)
2. 대회 or 인턴 (https://www.acmicpc.net/problem/2875)
3. 택배 (https://www.acmicpc.net/problem/8980)
4. 멀티탭 스케줄링 (https://www.acmicpc.net/problem/1700)
5. 보석 도둑 (https://www.acmicpc.net/problem/1202)
6. 빵집 (https://www.acmicpc.net/problem/3109)
7. 크게 만들기 (https://www.acmicpc.net/problem/2812)
8. 캔디캔디 (https://www.acmicpc.net/problem/2878)
9. 풍선 (https://www.acmicpc.net/problem/4716)
10. 박스 채우기 (https://www.acmicpc.net/problem/1493)
11. 숫자 게임 (https://www.acmicpc.net/problem/2923)
12. 통나무 자르기 (https://www.acmicpc.net/problem/1114)
13. 회의실 배정 (https://www.acmicpc.net/problem/1931)
14. 도서관 (https://www.acmicpc.net/problem/1461)
15. 행렬 (https://www.acmicpc.net/problem/1080)
16. 등수 매기기 (https://www.acmicpc.net/problem/2012)
17. 비슷한 순열 (https://www.acmicpc.net/problem/2413)

결과

이 글에서는 이 문제들 중 스터디원들이 어려워하였던 문제들 일부의 풀이를 다뤄보도록 하겠습니다.

H. 캔디캔디

주어진 사탕의 개수가 $M$개, 친구들이 $N$명이 있고, 각각의 친구들은 받고 싶은 사탕의 개수인 $A_i$ 가 주어집니다. 각각의 친구들에게 나눠준 사탕의 개수를 $B_i$ 라고 할 때, 이 개수를 적절히 정하여

$\sum{max(0, A_i - B_i)^2}$

의 최솟값을 구하는 문제 입니다. 즉, $B_1+B_2 + … + B_n \leq M$ 이 성립할 때 위 식의 최솟값을 구하는 문제 입니다.

우선, 편의를 위해 $S = A_1 + A_2 + … + A_n$ 이라고 할 때 $S > M$ 인 상황만을 가정하겠습니다. $S <= M$ 인 경우는 답이 $0$ 인 것을 쉽게 알 수 있기 때문입니다.

또한, 상식적으로 사탕을 원하는 양을 초과해서 주지는 않을 것입니다. 따라서 $i$ 번째 친구가 “못받은 사탕의 개수” 를 $C_i$ 로 정의하면

$0 \leq C_i \leq A_i$

$\sum{C_i} = M - S$

가 성립할 것이고, 문제는 이 때 $\sum{C_i^2}$ 을 최소화 하는 것으로 바뀌었습니다.

이제 언어의 편의를 위해 $C_i$ 를 받은 사탕이라고 생각하여 문제를 다시 정의합시다. 즉, 사탕은 총 $M - S$개가 있고, $i$ 는 사탕을 최대 $A_i$개 받을 수 있을 때, (받은 사탕수)$^2$ 의 합을 최소화 하는 것이죠

우선 변형된 문제를 이해하셨다면…

풀이를 찍어봅시다!

여러가지 관찰을 해본다면 분명히 받은 사탕의 개수가 서로 비슷할 때가 최적일 것이라는 느낌이 강하게 오고, 실제로 이것을 명확하게 정의하여 풀면 정답을 받을 수 있습니다.

여기서는 이 풀이가 성립하는 이유를 보다 정확히 알아봅시다!

만일 못받은 양이 공정하지 않은 두 친구 $i, j$ 가 있어서 $C_i + 1 < C_j$ 라고 합시다. 단, $C_i < A_i$ 인 상황입니다. 즉, $i$ 는 사탕을 더 받을 수 있음에도 불구하고 이미 더 많은 $j$ 한테 준 너무나도 불공정한 상황입니다.

우리가 원하는 최적해중에는 이런 불공정한 상황이 없는 것이 적어도 하나 있다는 것을 간단하게 증명할 수 있습니다.

$C_i + 1 < C_j$ 일 때, $C_i^2 + C_j^2 > (C_i + 1)^2 + (C_j - 1)^2$

이 성립하기 때문입니다. 한마디로 저런 불공정한 상황 대신에 $i$ 가 $j$ 로부터 사탕 하나를 기부 받아 한결 공정해진 상황이 더 좋은 상황이라는 얘기죠.

즉, 저희는 이러한 불공정한 상황이 없는 공정한 상황에 대해서만 고민을 해봐도 최적해를 얻을 수 있다는 것입니다.

한편, 어떤 공정한 상황 에 대해서 받은 사탕의 최댓값 $X$ 를 정의해 봅시다. 그러면 각 사람들이 받은 사탕의 개수가 재한적이게 됩니다.

구체적으로 $A_i < X$ 이면 무조건 $A_i$개의 사탕을 받아야만 합니다. 그렇지 않다면 $X$ 개를 받은 친구와 비교했을 때 공정하지 않기 때문입니다. 마찬가지의 이유로 나머지 친구들은 $X - 1$개 혹은 $X$개를 받았어야만 합니다.

이러한 제한적인 상황을 이용하면 아래와 같은 이분 탐색을 통해 공정한 상황이 언제인지를 찾을 수 있습니다.

int s = 1, e = mxval; // mxval 은 A[i] 중 최댓값
while(s <= e) {
	int m = (s + e)>>1;
	
	// 받은 사탕의 최대 개수가 m이라고 가정할 때
	long long need = 0;
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if(A[i] < m) need += A[i];
		else {
			need += m - 1;
			cnt++;
		}
	}
	if(M - S < need + 1) {
		// 이러한 상황을 만드려면 사탕이 너무 많이 필요하다. 불가능
		e = m - 1;
	}
	else if(need + cnt < M - S) {
		// 이러한 상황을 만드려면 사탕이 남는다. 불가능
		s = m + 1;
	}
	else {
		// 공정한 상황!
		break;
	}
}

또한 위의 코드를 보면 공정한 상황이 유일할 것임을 알 수 있으므로 우리는 발견한 공정한 상황에서 구하고자 하는 값이 몇인지를 계산하기만 하면 됩니다!

J. 박스 채우기

주어진 $A * B * C$ 크기의 박스를 한변의 길이가 $2^i$ 꼴인 정육면체들로 채울 때, 필요한 정육면체의 최소 개수를 구하는 문제 입니다.

단, 한 변의 길이가 $2^i$인 정육면체는 최대 $cnt_i$ 개 사용할 수 있습니다.

우선, 정육면체 개수에 재한이 없다면 어떻게 채워야 최적일지에 대해서 먼저 생각해보겠습니다.

$A, B, C$ 를 이진법으로 표현한 것이 아래와 같다고 합시다 $A = 2^{a_1} + 2^{a_2} + … + 2^{a_x} (a_1 < a_2 < … < a_x)$ $B = 2^{b_1} + 2^{b_2} + … + 2^{b_y} (b_1 < b_2 < … < b_y)$ $C = 2^{c_1} + 2^{c_2} + … + 2^{c_z} (c_1 < c_2 < … < c_z)$

이제 박스를 적절히 분리하면 $2^{a_i} * 2 ^{b_j} * 2^{c_k}$ 꼴의 직육면체가 $xyz$ 개 나오게 할 수 있다는 것을 알 수 있습니다.

각각의 직육면체를 채우는 최적의 방법은 무엇일까요? 당연히 $2^{min(a_i, b_j, c_k)}$ 인 정육면체들로 모두 채워버리는 것입니다.

각각의 직육면체를 이와 같은 방법으로 채워 넣으면 그것이 개수에 재한이 없는 경우의 최적의 방법입니다.

이 방법이 최적해를 구한다는 것을 증명해 보겠습니다.

우선 박스 형태(직육면체)라는 제한에서 벗어나 보겠습니다.

그러면 단순히 $A * B * C$ 를 $2^{i^3}$ 꼴의 합으로 나타낼 때 항의 최소 개수를 구하는 문제가 됩니다. (이 때, $2^{i^3}$ 의 계수를 $d_i$ 라고 합시다.)

이 문제는 제한을 너무 완화해서 실제 문제보다 더 좋은 답을 찾을 수도 있습니다. 하지만 다음의 조건을 추가하여 보겠습니다.

$2^i * d_i + 2^{i + 1} * d_{i + 1} + … \leq A_i * B_i * C_i$ ($1 \leq i$) (단, $A_i$ 는 $A$의 이진수 표현에서 $i$번째 미만의 비트는 버린값)

이 조건을 추가한 문제는 명백히 박스형태라는 제한이 있는 문제보다는 조건이 완화되어 있습니다(박스라는 제한이 저 조건을 포함하고 있기 때문).

그렇기 때문에 이 문제의 답은 박스 제한이 있을 때의 답보다 같거나 좋은 답을 찾게 됩니다. 한편, 위의 조건을 만족시키는 최적의 답은 우리가 위에서 언급한 방법임을 식을 비교해 보면 쉽게 알 수 있습니다.

따라서 위에서 언급한 방법이 박스형태라는 제한이 있는 문제의 최적해를 구하는 것을 증명하였습니다.

이제 $2^i$ 꼴의 정육면체의 개수의 제한이 있을 때의 경우를 살펴 봅시다! 위의 풀이를 알았다면 이 문제는 간단하게 풀 수 있습니다.

1. 우선 개수의 제한이 없을 때 필요한 정육면체의 개수를 크기 별로 구해줍니다.

2. 이제 크기가 큰 정육면체부터 보면서 사용할 수 있는 최대로 사용해주고 다 못채웠다면 못채운 정육면체들을 절반크기의 정육면체 8개로 분할해주는 것을 반복해주면 됩니다. (만일 못채웠는데 분할해줄 수 없다면, 채우는 것이 불가능합니다.)

이 방법이 동작하는 이유도 위의 증명과 비슷하게 할 수 있습니다

int ans = 0;
for(int i = 22; i >= 0; i--) {
	ans += min(need[i], cnt[i]);
	need[i] -= cnt[i]
	if(need[i] > 0) {
		if(i == 0) {
			// 불가능
			return 0;
		}
		need[i - 1] += 8 * need[i];
	}
}