[BOJ] 백준 11507 - 오르막 수 (자바)

규칙만 찾으면 정말 금방 풀 수 있는 문제이다.

DP 문제는 일단 경우를 모두 써서 규칙을 찾아내는 게 중요하다고 배웠다.

그래서 무작정 경우를 작성해보았다.

위 표와 같은 결과가 나온다.

위 표에서 DP[] 라는 배열을 할당했을때

 - 0은 횟수(N)이 증가함에도 상관없이 1임을 알수 있었다.

 - 1~9는 횟수(N)이 1일때를 제외하고, 이전에 있던 자신의 값과 바로 전값의 합임을 알 수 있었다.

즉,  dp[i] = dp[i]  dp[i - 1] 이라는 규칙을 얻어 낼 수 있었다.

<소스코드>

import java.io.FileInputStream;
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        //Scanner sc = new Scanner(new FileInputStream("input.txt"));
 
        int N = sc.nextInt();
 
        int[] dp = new int[10];
        int result = 0;
        for (int i = 0; i < 10; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < N; i++) {
            result = 0;
            for (int j = 1; j < 10; j++) {
                dp[j] = (dp[j] + dp[j - 1]) % 10007;
                result = (result + dp[j]) % 10007;
            }
        }
        if(result==0){
            System.out.println(10);
        }
        else
        System.out.println((result + 1) % 10007);
    }
}