[BOJ] 4811 알약 - Python

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

4811번: 알약

DP 문제이다.

첨에는 생각이 나지않아 안풀렸지만

종이를 가져와서 적어보았다

 

먼저 W랑 H는 무조건 한 세트여야 하고, W가 한개가 나와야 H가 나올 수 있음을 기억하자.

2 개가 있으므로 2차원 배열을 선언했다.

 

세로 컬럼은 W, 가로 행은 H로 두고 각각의 숫자는 나온 개수라고 하자.

그러면 H가 1이고 W 가 0일 수는 없다.

 

그래서 먼저 W가 1일때를 보자

W H	0	1	2	3
0	0	1
1	x
2
3

여기서 보면 H가 무조건 한개가 나올 수 있으므로 아래에 (1,1) 에 채워준다

W H	0	1	2	3
0	0	1
1	x	1
2
3

 

H가 2, W가 1은 안되므로 x

W가 2일때를 보면 방법이 두개인건 아니다. WW 가 나와야 하기 때문(H는 한개도안나옴)

W H	0	1	2	3
0	0	1	1
1	x	1
2		x
3

 

이 다음에 H가 1개 나올때는 WHW, WWH 이런식으로 나올 수 있기 때문에, WH가 세트로 1개일때 나왔던 경우의수 + W가 한개일때 경우의수를 더한다.

W H	0	1	2	3
0	0	1	1
1	x	1	2
2		x
3

이렇게 되면 대충 보인다.. 각 칸은 왼쪽 + 위쪽 이다!!

나는 실제로 W가 4개일때까지 손으로 써보면서 했다..

W H	0	1	2	3
0	0	1	1	1
1	x	1	2	3
2		x	2	5
3			x	5

 

 

arr = [[0] * 31 for _ in range(31)]
for i in range(1, 31):
    arr[0][i] = 1
for i in range(1, 31):
    for j in range(i, 31):
        arr[i][j] += arr[i-1][j] + arr[i][j-1]
while True:
    N = int(input())
    if N == 0:
        break
    print(arr[N][N])