[boj] (s1) 11051 이항 계수2
✅ DP ✅ Top Down
문제
풀이
1. 문제 접근 및 해결 로직 (풀이법)
이항 계수 성질에 의해 다음 식을 만족한다.
-
재귀를 사용하고 동일한 연산을 반복해서 수행하는 것을 방지하기 위해 메모이제이션을 활용한다. -> 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. 시간 복잡도 분석
경우의 수를 모두 구하므로
4. 문제에서 중요한 부분
DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항
Author And Source
이 문제에 관하여([boj] (s1) 11051 이항 계수2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@peanut_/boj-s1-이항-계수2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)