[ 2023-02-24 👧🏻 TIL ]

백준 11051번

풀이코드

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[1] for i in range(n+1)] #처음에는 무조건 1로 시작하기에 1을 넣어줌

dp[1].append(1)  # 현재 dp == [[1], [1,1]] 

for i in range(2, n+1):
    for j in range(1, i+1):
        if j == i:
            dp[i].append(1) # 마지막이 무조건 1로 끝나기에 1을 넣어줌
        else:
            dp[i].append(dp[i-1][j-1] + dp[i-1][j]) 
            # 이전 행(i-1)의 이전 열(j-1)과 이전 행의(i-1) 현재 열(j)의 값이 더한 값이 
       
## print(dp[n][k] % 10007)

두 입력되는 N, K의 이항 계수를 10007로 나눈 나머지 값을 구하는 코드를 작성하는 문제입니다.

처음에는 재귀를 이용한 방법으로 문제를 해결하려 했으나, 문제에서 제공되는 N과 K의 범위가 1000까지 제공되기에 에러가 발생하였습니다.

이를 해결하지 못하여 풀이방법을 찾아보게 되었고 DP(동적 계획법)알고리즘을
파스칼의 삼각형 공식에 적용하여 문제를 해결하였습니다.

DP(동적 계획법)

DP는 상위 문제를 여러 개의 하위 개념으로 나누어 그 결과를 가지고 상위 문제를 해결하는 방법입니다.

위에 문제에서는 하위 문제 (위에서 아래로 1~n+1까지의 줄이 있을 때 n-1줄에 k-1, k의 위치) 에 있는 두 개의 수를 더함으로서 상위를 문제 (n줄의 k의 값) 을 해결 할 수 있는 것을 확인 할 수 있습니다.

처음과 끝은 1이고 나머지는 (n-1, k-1) + (n-1, k) = (n, k)이라는
이전의 값을 참조하여 현재의 값을 알아내야 하기에 DP를 사용할 수 있었습니다.