[백준]4811 알약 #dp#조합

1. 풀이

(1) 약 한알을 다먹었을때 w, 반개만 먹었을때 H이므로 나올수있는 경우는 약이 2개일때 WWHH를 적절히 조합한 경우.

(2) 이때 고려해야할 점은 약이 반개가 남으려면 그 전에 한개를 쪼갠적이 있어야한다. 즉 앞에서부터 순서대로 진행할 때 H의 개수가 W의 개수보다 많으면 안된다. (HW(X),WHH(X),WHWHH(X))

(3) 따라서 아래와 같은 점화식을 만들 수 있다.

DP[i][j] : 알약반개 i번, 알약한개를 j번 먹었을때 경우의 수

그리고 이는

알약반개를 i-1번먹고, 알약한개를 j번먹은상태 (dp[i-1][j]) 에서 알약 반개를 먹는경우 +

알약한개를 i번먹고, 알약반개를 j-1번먹은상태(dp[i][j-1])​ 에서 알약 한개를 먹는경우의 합이된다.

=> 즉 dp[i][j]=dp[i-1][j]+dp[i][j-1]

​

*주의할점

- 모두 알약 한개를 먹는경우인 dp[0][j]는 한가지 경우이므로 1로 채움

- 쪼개진 알약이 없는데 반개를 먹는경우(dp[i][j] , (i>j))는 없으므로 모두 0

 

2. 소스코드

dp=[[0 for j in range(31)] for i in range(31)]
for j in range(31):
    dp[0][j]=1
for i in range(1,31):
    for j in range(i,31):
        dp[i][j]=dp[i-1][j]+dp[i][j-1]


while(1):
    N=int(input())
    if N==0:
        break
    else:
        print(dp[N][N])