[DP]문제#5.오르막수(★)

11057번: 오르막 수 (acmicpc.net)

 

--누적해서 정리

1. 여기서는 먼저 9로시작하는 경우에 경우의수는 1개라는 사실을 이용하는 것이 좋다

EX)9_ ->1가지

    9_ _ ->1가지

 

2. D[N][0]:길이가 N인 0으로 시작하는 오르막수의 개수 ~ 9로시작

   D[N][8]: 길이가 N인 8로 시작하는 오르막수의 개수 ~ 9로시작

 

11057번: 오르막 수

import java.util.Scanner;

public class Main {

	static int[][] d;
	static int N;
	public static void main(String[] args) {
		
		Scanner in=new Scanner(System.in);
		N=in.nextInt();
		
		d=new int[N+1][10]; 
	
		d[1][9]=1;
		for(int i=8;i>=0;i--) d[1][i]=d[1][i+1]+1;
       
		for(int a=2;a<=N;a++) {
			d[a][9]=1;
			for(int i=8;i>=0;i--) {
			d[a][i]=(d[a-1][i]+d[a][i+1])%10007;
		}
			}
		System.out.println(d[N][0]);
		}
		
}