[java] 백준/11057 오르막 수

dreammarker 2019. 4. 9. 17:10

1자리일때는 1개씩

dp[n][l] n은 자리수 l은 마지막수

dp[1][l] l -> 0~9 까지 1로 초기화

dp[n][l] = dp[n-1][0]+dp[n-1][1]+dp[n-1][2]+....+d[n-1][l]

이걸 코드로 하면..

package basic;

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class AscendingStair {

public static void main(String[] args) throws Exception{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n = new Integer(br.readLine());

long dp[][] = new long [n+1][10];

for(int i=0;i<10;i++){

dp[1][i] = 1;

}

for(int i=2;i<=n;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] = dp[i-1][0] + dp[i-1][1] +... + dp[i-1][j]

}

dp[i][j] %=10007;

}

int ans =0;

for(int i=0;i<10;i++)

ans+=dp[n][i];

System.out.println(ans%10007);

}