코테/BOJ

백준 4811 [알약] 파이썬

동 캄 2022. 9. 19. 17:04
반응형

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

 

4811번: 알약

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

www.acmicpc.net

# 백준 4811 알약
import sys
input = sys.stdin.readline
ans = [0]*(32)
dp = [[0]*32 for _ in range(32)]
for i in range(1, 32):
    dp[i][0] = 1
for i in range(1, 32):
    for j in range(1, i+1):
        dp[j][i] = dp[j-1][i]+dp[j][i-1]
    # dp[j+1][i]=dp[j][i]

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

 

다이나믹 프로그래밍을 이용해서 문제를 해결한다. (2차원 배열 이용)

반응형