[백준] 4811 알약 with Python

📌 BOJ 4811 알약

💡 조건

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

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

3. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다.

4. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다.

5. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

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

7. 다이나믹프로그래밍 유형의 문제

🖥 소스 코드

from sys import stdin

arr = [[0] * 31 for _ in range(31)]
arr[0][1] = 1
for i in range(31):
    for j in range(i, 31):
        if i == 0:
            arr[i][j] = 1
        else:
            if i == j:
                arr[i][j] = arr[i-1][j]
            else:
                arr[i][j] = arr[i-1][j] + arr[i][j-1]

while 1:
    n = int(stdin.readline())
    if n == 0:
        break

    print(arr[n][n])

🔖 예제 및 실행결과

예제

6
1
4
2
3
30
0

실행결과

132
1
14
2
5
3814986502092304

⌨️ 문제 풀이

1. 알약을 먹지 않으면 절대로 반개짜리는 존재할 수도 없다.

2. 온전한 알약을 먹으면 반쪽짜리 알약이 생긴다.
   이 경우, 반쪽짜리 알약을 먹을 수 있는 경우의 수가 하나 더 늘어난다.

3. h/w 0 1 2 3 4
   0 0 1 1 1 1
   1 1 2 3 4
   2 2 5 9
   3 5 14
   4 14

💾 느낀점

1. 다이나믹프로그래밍을 너무 못한다.
2. 문제를 이해하고, 이해한 내용을 바탕으로 풀이를 유도하는 것이 아예 되지를 않는다.
3. DP 문제같다고 생각이 되면 천천히 그려가면서 생각을 해보자.