[BOJ] 백준 4811번 : 알약 (JAVA)

문제

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

 

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

 

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

 

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

 

 

입력

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

 

 

출력

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

 

 

풀이

다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였습니다.

 

문제만 봐서는 바로 로직이 떠오르지 않으니 N = 1부터 천천히 나열해 봅시다.

 

 

N = 1일 때는, 큰 알약을 하나 먹고, 작은 알약을 하나 먹는 WH 방법으로, 1가지가 있습니다.

 

 

 

N = 2일 때는, 큰 알약을 먹는 동시에 2가지 케이스로 나뉘게 됩니다.

 

 

1) 작은 알약 -> 큰 알약 => 1가지

 

 

2) 큰 알약 -> 작은 알약 => 1가지

 

 

총 2가지입니다.

 

 

 

N = 3일 때는 큰 알약을 먹는 동시에 3가지 케이스로 나뉘게 됩니다.

 

 

1) 작은 알약 -> 큰 알약 -> 큰 알약

 

=> 작은 알약을 먹고나면, 큰 알약 2개가 남는데, 이것은 dp[2] = 2 가지와 동일합니다.

 

수식 : dp[0] * dp[2]

 

 

2) 큰 알약 -> 작은 알약 -> 큰 알약

 

=> 큰 알약을 먹고나면, 작은 알약 -> 작은 알약 -> 큰 알약으로, 1가지 입니다.

 

수식 : dp[1] * dp[1]

 

 

3) 큰 알약 -> 큰 알약 -> 작은 알약

 

=> 앞에 큰 알약 2개는 dp[2] = 2가지와 같고, 작은 알약은 케이스를 구분하는 데 영향을 끼치지 않으므로 2가지가 됩니다.

 

수식 : dp[2] * dp[0]

 

따라서 총 5가지가 됩니다.

 

 

이제, 제가 위에서 써 놓은 수식을 봅시다.

사실상, 작은 알약을 기준으로 왼쪽 사건의 경우의 수와 오른쪽 사건의 경우의 수를 곱한다는 것을 알 수 있습니다.

따라서, k번째 알약의 문자열 개수를 구하는 방법은 합이 N - 1로 나누어지는 두 요소 i, j를 찾고,

dp[i] * dp[j] 를 한 값을 dp[k]에 저장하는 것입니다.

 

즉, dp[k] = dp[i] * dp[N - 1 - i] 라고 점화식을 정의할 수 있습니다.

이제, 점화식을 정의하였으니 bottom-up 방식으로 코드를 작성하시면 됩니다.

 

 

자세한 내용은 아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.