[백준 11057] 오르막 수(Java)

1. 문제

www.acmicpc.net/problem/11057

11057번: 오르막 수

2. 풀이

• 점화식을 만드는데 많은 시간을 사용했다ㅠㅠㅠ
• 길이가 1일 때 0~9는 전부 1번씩 쓰인다.
  길이가 2일 때 0=00(1번), 1=01,11(2번), 2=02,12,22(3번), 3=03,13,23,33(4번) .......
  길이가 3일 때 0= 1번, 1=3번, 2=6번, 3=10번....
  만약 길이 3 일때 3의 오르막 개수를 알고 싶다면, 길이 2일때의 0,1,2,3 을 다 더하면 10이라는 것을 알 수 있다.

3. 코드

import java.util.Scanner;

public class Main {

	static final int mod =10007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int[][]dp = new int[num+1][10];
		
		for(int i =0; i<10; i++) {
			dp[1][i] =1;
		}
		
		for(int i =2; i<=num; i++) {
			for(int j =0; j<10; j++) {
				for(int k =0; k<=j;k++) {
					dp[i][j] = dp[i][j]+dp[i-1][k];
					dp[i][j] %=mod;
				}
			}
		}
		int sum=0;
		for(int i =0; i<10; i++) {
			sum+=dp[num][i];
		}
		System.out.println(sum%mod);
		
		
	}

}

반응형