For a better world

import sys
input = sys.stdin.readline

N = int(input())

DP = [0] * (1000 + 1)
DP[1] = 1
DP[2] = 2

for i in range(3, 1000+1):
    DP[i] = DP[i-2] + DP[i-1]

print (DP[N] % 10007)

이 문제를 해결하는 데는 두 가지 방법이 존재함.

두 문제에 공통적으로 사용되는 요소는 조합.

조합 = 서로 다른 n개 중에 r개를 선택하는 경우의 수 의미.

${}_nC_r = {n! \over (n-r)!r!}$

1. 다이나믹 프로그래밍 적용 X

def factorial(N):
    if N > 1:
        return (N * factorial(N-1))
    else:
        return 1

T = int(input())
for _ in range(T):
    N, M = list(map(int, input().split()))
    print (factorial(M) //  (factorial(M-N) * factorial(N)))

2. 다이나믹 프로그래밍 적용 O

T = int(input())
dp = [[0] * 30 for _ in range(30)]
for i in range(30):
    for j in range(30):
        if i == 1:
            dp[i][j] = j
        else:
            if i == j:
                dp[i][j] = 1
            elif i < j:
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

for _ in range(T):
    N, M = list(map(int, input().split()))
    print (dp[N][M])