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

 

오르막 수 문제보기

11057번: 오르막 수

 

문제 설명
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다.
이때, 인접한 수가 같아도 오름차순으로 친다.
예를들어, 2234와 3678, 11119는 오르막 수이지만,
2232, 3676, 91111 은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오
수는 0으로 시작할 수 있다.

입력
첫째 줄에 N( 1 <= N <= 1,000)이 주어진다.

출력
첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

 

처음에 테스트케이스를 가지고 문제에 접근을 했습니다..

완전 이상한 행동을 했죠.

뭔가 테스트 케이스에서 1~3까지 나온 출력 값이 10 / 55 / 220 이 두 수의 합공식인 n(n+1)/2 공식과 연관이 있다고 생각해서 계속해서 테스트 케이스를 가지고 접근을 했습니다.

결국 규칙을 찾지 못하고

N이 2일 때까지 수를 나열해서 보니깐 0~9까지 수가 반복적인 패턴을 찾았습니다.

 

N이 1일 때는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 라는 수가 필요하고

N이 2일 때는, 00~09, 11~19, 22~29, 33~39, 44~49, 55~59, 66~69, 77~79, 88~89, 99 의 경우의 수가 더해질 것입니다.

여기까지 생각하고, 0~9까지가 N이 3일 때도 연관이 있을 거라는 생각을 했습니다.

그래서 표를 그려서 확인하면 확실하게 규칙을 알 수가 있었습니다.

 

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
1	2	3	4	5	6	7	8	9	10
1	3	6	10	15	21	28	36	45	55
1	4	10	20	35	56	84	120	165	220

점화식은 DP[N][J] = DP[N][J-1] + DP[N-1][J] 입니다. (J는 0~9 까지의 수입니다)

아래 코드는 성공한 코드입니다

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

public class Main {
    static long DP[][];
    static final int MOD = 10_007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        DP = new long[N+1][10]; //0~10
        // 보기(1)을 사진을보면 아래 코드에 담기는 걸 확인할 수 있습니다.
        Arrays.fill(DP[0], 1);
        for (int i = 1; i < DP.length; i++) {
            DP[i][0] = 1;
        }

        for (int i = 1; i < DP.length; i++) {
            for (int j = 1; j< DP[i].length; j++) {
                DP[i][j] = (DP[i][j-1] + DP[i-1][j]) % MOD;
            }
        }
        System.out.println(DP[N][9]);
    }
}

보기 (1)