[백준] 11057번 오르막 수

https://www.acmicpc.net/problem/11057

 

 

동적계획법(Dynamic Programming)으로 푼 문제다.

 

* ascending[N][L] : 길이가 N이고 마지막 수가 L인 오르막 수

 

그 직전의 자리수(i-1)에서 마지막 값(j)을 한번 더 반복한 경우의 수가 ascending[i-1][j]이므로 ascending[i][j]에 더해주고,

 

그 직전의 자리수(i-1)에서 마지막 값(j)부터 9까지의 경우의 수(k)를 각각 더해주면 된다.

 

Overflow가 발생할 수 있으니 연산 중간에 10,007로 꼭 나눠주고, 마지막에 출력할 때도 나눠준다.

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] ascending = new int[N + 1][10];
        for(int j = 0 ; j <= 9 ; j ++)
            ascending[1][j] = 1;

        for(int i = 2 ; i <= N ; i++){
            for(int j = 0 ; j <= 8 ; j++) {
                ascending[i][j] = ascending[i - 1][j];
                for(int k = j+1 ; k <= 9 ; k++)
                    ascending[i][j] = (ascending[i][j] + ascending[i - 1][k]) % 10007;
            }
            ascending[i][9] = ascending[i-1][9];
        }
        int answer = 0;
        for(int a : ascending[N])
            answer += a;
        System.out.println(answer%10007);
    }
}

 

 

위의 코드는 처음 채점번호 21977625이다.

21978172는 다른 방식으로 푼 사람의 코드를 참고하였다. 크게 다르진 않았다.