백준 4811 - 알약

이번 문제는 백준의 골드 5 문제 알약 문제이다.
문제를 차근차근 한번 읽어보도록 하자.

선영이가 할아버지에게 최대 30개의 알약이 담긴 약통을 준다.
첫 날, 할아버지는 약을 하나 꺼내 반으로 쪼개고 반 쪽만 먹는다.
다음 날 부터 할아버지는 반을 꺼낼 수도 있고 하나를 꺼낼 수도 있다.
반 조각이라면 H를 보내고 그 약을 먹도록 하고,
한 조각이라면 W를 보내고 그 약을 반으로 쪼개 반만 먹는다.

이 때 만들어질 수 있는 문자열의 총 개수를 구하라!
상당히 신기한 문제같다. 어떻게 풀어야 할까?

1차원 DP

문제를 읽어보았을 때 핵심은, 문자열의 개수 를 구해야한다는 것이다.
그 말인 즉, 문자열을 구하는 것이니 DFS나 BFS를 사용할 필요는 없다.
따라서 나는 DP의 Memoization을 이용하려 한다.

그럼 DP를 사용하기로 결정했으니, 점화식을 세워야 한다.
기저 조건부터 한번 생각해보자.

약이 1개이면 반드시 반으로 쪼개어 약을 먹는다.
즉, 만들어질 수 있는 문자열은 WH 뿐이다.

약이 2개이면 어떻게 될까?
우선 첫째 날에는 반드시 W가 올 수 밖에 없다.
둘째 날에는 WH가 될 수도 있고 WW가 될 수도 있다.

이제 둘째 날에 먹는 약에 따라 분기가 갈리게 된다.

  1. WH를 먹는 경우
    • 이후 WHWH 밖에 올 수 없다.
    • 약이 반드시 한 알이 남기 때문이다.
  2. WW를 먹는 경우
    • 이후 WWHH 밖에 올 수 없다.
    • 약이 반드시 반 알 두 개가 남기 때문이다.

약이 3개일때도 한 번 계산해 보자.
첫째 날에는 어쩔 수 없이 W가 온다. 둘째 날에는 WH혹은 WW가 온다.
셋째 날에는 WHW, WWH, WWW가 가능하다.

어? 세 개 부터는 분기가 더 늘어나게 된다.

  1. WHW를 먹는 경우
    • WHWH, WHWW가 될 수 있다.
    • 이후 WHWHWH, WHWWHH가 될 수 밖에 없다.
  2. WWH를 먹는 경우
    • WWHW, WWHH가 될 수 있다.
    • 이후 WWHWHH, WWHHWH가 될 수 밖에 없다.
  3. WWW를 먹는 경우
    • 최종적으로 WWWHHH 밖에 올 수 없다. 즉 약이 3개일 땐, 5가지의 문자열을 만들 수 있다.

Memoization이라 함은, 이전 단계에서 계산한 것을 사용할 수 있어야 한다.
어떻게 규칙을 찾아 이전 단계의 것을 이용할 수 있을까?

곰곰히 생각해보았지만, 도저히 규칙이 없음을 깨닫고 생각을 고쳤다.
아예 새로운 방식으로 접근해보자.

2차원 DP

2차원 배열을 사용한다고 생각해보자. DP[w][h]와 같이 말이다.
행은 W, 알약 한 알이 되고 열은 H, 알약 반 알이 된다.
DP[w][h]는 w개와 h개의 알약을 먹을 수 있는 경우의 수이다.

먼저, DP[0][1]과 같은 경우는 어떨까?
W를 먹지 않고서는 H가 생겨나지 않아, 불가능하다.
즉 W는 항상 H보다 크거나 같아야 함을 알 수 있다!

다음으로, DP[1][0]과 같이 W만 먹는 경우는 어떨까?
DP[2][0], DP[3][0]..은 모두 WWW...가 된다.
즉 단 하나의 문자열만을 만들 수 있는 것이다.

그렇다면 이제 DP[3][2]와 같이 다양하게 먹는 경우라면?
WWWHH WWHWH와 같이 여러 문자열이 나올 수 있을 것이다.
생각을 잠깐 해보면 둘이 합쳐 길이가 5인 문자열을 만든다는 말인데..
이는 길이가 4인 문자열에 대해서 W와 H를 합쳐 만들 수 있다.

즉 우리는 DP[w][h] = DP[w-1][h] + DP[w][h-1]로 문자열을 만들 수 있다!
최종적으로 아래와 같이 구현할 수 있다.

int tc = 0;
long long dp[31][31];
void fill_dp() {
	for (int w = 0; w <= 30; w++) {
		for (int h = 0; h <= 30; h++) {
			if (h > w)
				continue;
			if (h == 0)
				dp[w][h] = 1;
			else
				dp[w][h] = dp[w - 1][h] + dp[w][h - 1];
		}
	}
}

int main() {
	fill_dp();
	while (true) {
		cin >> tc;

		if (tc == 0)
			break;

		cout << dp[tc][tc] << '\n';
		// W, H를 모두 먹어서 만들 수 있는 문자열
	}

	return 0;
}

사실 이전에 풀었던 경험이 있는 문제인데,
요즘 DP에 약해진 것 같아 다시 복기하기로 결심했다.
다시 풀어보니 역시 문제를 풀기가 힘들었다.
사고력이 부족한 것에 더해 공부량이 아직 많이 부족한 것 같다.