[백준]4811(파이썬) - 알약

https://www.acmicpc.net/problem/4811

4811번: 알약

 

• 이 문제는 꽤나 까다로웠던 문제입니다. 이 문제를 빠른 시간 내에 풀 수 있다면 DP관련 문제들은 웬만한 건 해결할 수 있겠다는 생각이 들었죠.먼저 DP로 푸는 문제인 거 같다! 라는 생각을 했고 DP문제를 푸는 과정을 정리해봤습니다.
  • DP는 이전 결과가 다음결과에 영향을 미쳐야 합니다.
  • DP를 풀 때 변수를 어떻게 정할지가 중요합니다.
  • 이전 결괏값을 가져다 쓰기 위해서는 초기화가 중요합니다.
• 위 세 가지 조건을 잘 생각하면서 문제를 풀었습니다.
• 이 문제에서 고려해야 할 변수는 h와 w 이기 때문에 각각 i, j 변수로 생각했고, 2차원 배열 DP를 그렸습니다. 역시 DP는 생각안 날 때는 무조건 손으로 그려보는 게 최고인 것 같습니다.

 

 

• 결과적으로 점화식을 위와 같이 구했고 자세한 설명은 주석을 참고해주시면 감사하겠습니다.

 

# 규칙을 찾아야한다.
# dp 문제이다.

import sys
input = sys.stdin.readline

dp = [[0 for _ in range(31)] for _ in range(31) ]
#i 는 w의 개수, j는 h의 개수로 dp[i][j] 는 w i 개 h j개로 만들 수 있는 경우의 수

#w가 없고 h 만 남아있다면 어차피 경우의 수는 h를 선택하는 방법 밖에 없기 때문에
#dp[0][h] 를 1로 초기화 해준다.
for j in range(1,31):
    dp[0][j] = 1

for i in range(1,31):
    for j in range(30):
        # h가 하나도 없을 때 w를 하나먹으면 h가 하나 무조건 생긴다.
        if j == 0:
            dp[i][j] = dp[i-1][j+1]
            # 반쪽 자리 j 가 하나라도 있으면 h 를 먹을 때와  w 를 먹을 때 두가지 경우를 구해서 더해준다.
        else:
            dp[i][j] = dp[i-1][j+1] + dp[i][j-1]

while 1:
    n = int(input())
    # 이 입력되면 입력을 멈춘다.
    if n == 0:
        break
    print(dp[n][0])