11057 오르막수

풀이코드

#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 10007;
// 11057

int main(){
	int dp[1001][10] ={0}, length;
	int result = 0;
	
	cin >> length;	
	
	for(int &x : dp[1]){
		x = 1;
	}
	
	for(int i = 2; i <= length; i++){
		for(int j = 0; j < 10; j++){
			for(int k = 0; k <= j; k++){
				dp[i][j] += dp[i - 1][k];
			}
			dp[i][j] %= mod;
		}
		
	}
	
	for(int i = 0; i < 10; i++){
		result += dp[length][i];
	}
	
	cout << result % mod << endl;
	
}

 

해설

10844 번 계단 수를 풀고 와서 그런지 점화식 자체를 구성하는 것은 쉬웠고 실제로 구현하는 것은 쉬웠다.

끝 수가 0이라고 생각하면 그 전 길이의 끝 수가 0인 것을 계승. 1이라면 0과 1. 2라면 0과 1과 2. ...

$$ a_{n k} = \displaystyle\sum_{j=0}^{k} a_{n-1 j} $$

이러한 방식이다.

하지만 제출할수록 틀리고 알 수 없는 답이 나오는 경우가 있었는데 찾다보니 결국 배열을 초기화 하지 않아서 생긴 문제 였다. dp 라는 배열은 계속 + 만 하는 배열이기에 초기화를 꼭 시켜줬어야 했다. 하지 않아서 dump 값이 중간에 들어가 오류가 발생하였다.