✅ DP ✅ Top Down

문제

링크

풀이

1. 문제 접근 및 해결 로직 (풀이법)

이항 계수 성질에 의해 다음 식을 만족한다.

$(N,K)=(N-1,K-1)+(N-1,K)$

• 재귀를 사용하고 동일한 연산을 반복해서 수행하는 것을 방지하기 위해 메모이제이션을 활용한다. -> DP의 Top Down 방법 사용

• N과 K가 같을 경우 이항 계수는 1, K가 0일 경우 이항 계수는 1이다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int memo[1001][1001]; // memo[N][K]
int N, K;

int dp(int N, int K)
{
    if (memo[N][K] != 0) // 이미 구한 값이면 저장해놓은 값 꺼내서 리턴 (메모이제이션)
        return memo[N][K];

    if (N == K || K == 0) memo[N][K] = 1;
    else memo[N][K] = (dp(N-1,K-1) + dp(N-1,K)) % 10007;

    return memo[N][K];
}

int main()
{   
    cin >> N >> K;
    
    dp(N, K);
    
    cout << memo[N][K] << "\n";

    return 0;
}

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항