[백준] 11057 오르막 수

www.acmicpc.net/problem/11057

11057번: 오르막 수

import java.util.Scanner;

public class Main11057 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int answer = 0;
		int dp[][] = new int[N+1][10];
		if(N == 1) answer = 10;
		else if(N == 2) answer = 55;
		else {
			for(int i = 0; i < 10; i++) {
				dp[1][i] = 1;
				dp[2][i] = i;
			}
			
			for(int i = 3; i <= N; i++) {
				for(int j = 1; j < 10; j++) {
					dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 10007;
				}
			}
			
			for(int j = 1; j <= N; j++) {
				for(int i = 0; i < 10; i++) answer += (dp[j][i] % 10007);
			}
		}
		System.out.println(answer % 10007);
	}
}

 

길이별로 0~9까지의 끝자리수를 계산 할 수 있도록 2차원 배열을 만들었다.

 

 

이런식으로 각각의 길이에 끝자리 수 별로 몇 개의 오르막 수가 있는지 세어 보면 규칙을 찾을 수 있다.

 

dp[3][9] = 45 = dp[2][9] + dp[2][8] + dp[2][7] + ..... + dp[2][1]

 

여기서 dp[2][8] + dp[2][7] + ..... + dp[2][1] 같은 경우에는 dp[3][8]이라고도 할 수 있다.

 

 

dp[3][1] = 1 = dp[2][1] + dp[3][0]

dp[3][2] = 3 = dp[2][2] + dp[3][1] = 2 + 1

dp[3][3] = 6 = dp[2][3] + dp[3][2] = 3 + 3

...

dp[3][9] = 45 = dp[2][9] + dp[3][8]

 

이 규칙을 점화식으로 아래와 같이 풀 수 있다.

	for(int i = 3; i <= N; i++) {
			for(int j = 1; j < 10; j++) {
				dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 10007;
		}
	}

 

---

%10007 부분을 처음에는 정답에만 넣어서 틀렸었다. 숫자를 계산할 때도 꼭 추가를 해줘야한다.