반응형
728x170
DP 중에서 하다보면 규칙을 찾는 것이다.
규칙을 2분만에 찾아서 바로 풀 수 있었다.
하지만 잘 보이지 않는다면.. 조금 힘들다.
항상 N-1과 N의 관계를 생각하면 될 것 같다.
https://www.acmicpc.net/problem/11057
#맞는 풀이
#include <iostream>
using namespace std;
int dp[1001][10];
int N;
int main(){
cin >> N;
//초기값
for(int i = 0; i<=9; i++){
dp[1][i] = 1;
}
// ex) dp[4][2] 는 dp[3][0] + dp[3][1] + dp[3][2] 이다.
// 3까지 0이었다면 2를 선택할 수 있고 3까지 1이었다면 2를 선택할 수 있고...
// 3까지 3이라면 2는 선택을 못하므로 제외
for(int i=2; i<=N; i++){
for(int j = 0; j<=9; j++){
for(int k = 0; k<=j; k++){
dp[i][j] += dp[i-1][k];
dp[i][j] %= 10007;
}
}
}
//N에서 모든 개수는 0으로 끝나는 것부터 9로 끝나는 것 모두 합치면 된다.
int ans = 0;
for(int i =0; i<=9; i++){
ans += dp[N][i];
ans %= 10007;
}
cout << ans;
}
코멘트로 달아놨다.
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 11053번, 가장 긴 증가하는 부분 수열 : C++ [CPP] (0) | 2021.12.29 |
---|---|
백준, BOJ, 11057번, 오르막 수 : C++ [CPP] (0) | 2021.12.28 |
백준, BOJ, 1915번, 가장 큰 정사각형 : C++ [CPP] (0) | 2021.12.27 |
백준, BOJ, 1389번, 케빈 베이컨의 6단계 법칙 : C++ [CPP] (0) | 2021.12.27 |
백준, BOJ, 2841번, 외계인의 기타 연주 : C++ [CPP] (0) | 2021.12.27 |