문제
https://www.acmicpc.net/problem/4811
70세 박종수 할아버지는 매일매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.
첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.
다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.
종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?
입력
입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.
예제
나의 풀이 (실패)
import sys
input = sys.stdin.readline
pills = []
while True:
N = int(input())
if N == 0:
break
else:
pills.append(N)
result = [0] * (max(pills) + 1)
def texting(n, str, w, h):
if len(str) == n*2:
result[n] += 1
return
if w < n:
texting(n, str + "W", w+1, h)
if h < n and h < w:
texting(n, str + "H", w, h+1)
for n in pills:
texting(n, "W", 1, 0)
print(result[n])- 재귀함수를 이용해서 `n`개의 약마다 서로 다른 문자열의 개수를 각각 구했는데 `n`이 커질수록 비효율적인 구조라 시간초과가 발생한다.
- 한 번에 `30`까지 계산하면서 `n`개마다 갯수를 추가하는 방법도 시도해 봤지만 `w`와 `h`의 짝을 맞추는 게 쉽지 않았다.
다른 사람의 풀이
import sys
input = sys.stdin.readline
# 약의 최대 개수만큼 2차원 리스트 생성
dp = [[0] * 31 for _ in range(31)]
# h만 남은 경우에는 경우의 수가 하나밖에 없다
for j in range(1, 31):
dp[0][j] = 1
for i in range(1, 31):
for j in range(30):
# h가 하나도 남지 않았다면 무조건 w를 먹어야 한다
if j == 0:
dp[i][j] = dp[i-1][j+1]
# w를 먹거나, h를 먹거나 두 가지 경우의 수를 더한다
else:
dp[i][j] = dp[i-1][j+1] + dp[i][j-1]
while True:
n = int(input())
if n == 0:
break
else:
# n개의 w가 있을 때 경우의 수 출력
print(dp[n][0])- 약의 최대 길이만큼 2차원 리스트를 생성하는데, 이때 `dp[i][j]`는 완전한 알약이 `i`개, 반 개의 알약이 `j`개 남아있을 때 만들 수 있는 경우의 수를 나타낸다.
- 약이 H만 남은 경우에는 `HHHH...`와 같이 H를 일렬로 나열하는 경우의 수밖에 없기 때문에 `dp[0][j]`를 모두 `1`로 초기화한다.
- `(i, j)` 즉 완전한 알약이 `i`개, 반 개의 알약이 `j`개 남아있을 때 할 수 있는 선택은 두 가지다.
- W 선택: 완전한 알약을 하나 꺼내서 반 개로 쪼갠다 -> `(i-1, j+1)`
- H 선택: 반 조각을 하나 먹는다 -> `(i, j-1)`
- 따라서 `(i, j)` 상태에서 만들 수 있는 경우의 수는 W를 선택한 경우의 수 + H를 선택한 경우의 수가 된다.
- `dp`의 모든 요소를 탐색하면서 이전 값을 이용해 현재의 값을 계산한다.
- 만약 H가 하나도 남지 않았다면 무조건 W를 먹는 선택을 내려야 한다. -> `dp[i][j] = dp[i-1][j+1]`
- 그 외의 경우에는 W를 먹은 경우의 수와 H를 먹은 경우의 수를 더한다. -> `dp[i][j] = dp[i-1][j+1] + dp[i][j-1]`
- 최종적으로 입력받은 약의 개수에 따라 N개의 완전한 알약이 있을 때 경우의 수, 즉 `dp[n][0]`을 출력한다.
회고
- 풀이를 봐도 이해가 안 돼서 오래 붙잡고 있었던 문제다. 지금도 완벽하게 이해가 되는 건 아니지만 어느 정도 접근 방식과 흐름은 이해가 된다.
- 나에게 절망을 안겨준 문제였지만, 이런 어려운 문제를 풀어봐야 성장할 수 있는 거겠지.
- 나중에 다시 한 번 풀어보고 싶어서 백준에 풀이는 제출하지 않고 [시도했지만 맞지 못한 문제]에 남겨두기로 했다.
