11057) 오르막 수 c++

문제 ) www.acmicpc.net/problem/11057

11057번: 오르막 수

 

풀이 ) 

1. N = 1 ( 수의 길이 N이 1일 때 )
   dp[1][0] = 1, dp[1][1] = 1, ... , dp[1][9] = 1 로 총 10개이다.
   다시말해서, 한 자리인 수는 0~9까지 총 10개이기 때문에 (문제에서 수는 0으로 시작할 수 있다고 명시됨).
   dp[1][0~9] 에 1을 대입해둬서 다 더했을 때, 총합을 10으로 만듦

2. N >= 2 ( 수의 길이 N이 2이상일 때 )

dp[j][i] = dp[j][i] + dp[j-1][k] 점화식을 이용해서 문제를 푼다

점화식이 잘 이해가 안되서 직접 다 써보았다.
문제에서 0부터 시작한다고 해서 N=2 일때는 00부터 숫자를 세야하고

N=3일때는 000부터 해야해서 앞에 N=1, N=2 일때도 포함되는 것같다...

 

 

코드 ) 

#include <iostream>
using namespace std;

int N;
int sum;
int dp[1001][10];
int main(void) {
    ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    
	cin >> N;
    
    // 1
	for(int i=0; i<10; i++) {
		dp[1][i] = 1;
	}
    
    // 2
	for( int j=2; j<=N; j++ ) {
		for( int i=0; i<10; i++ ) { // 3
			for( int k=0; k<=i; k++ )	// 4
				dp[j][i] = (dp[j][i] + dp[j-1][k]) % 10007;
		}
	}
    
	// 5
	for( int i=0; i<10; i++ ) {
		sum += dp[N][i];
	}
	
	cout << sum % 10007;
}