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

11057번

오르막 수

 

 

 

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

 

입력

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

 

출력

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

 

 

 

 

 

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

11057번: 오르막 수

---

1. 작은 문제의 답을 구하여 규칙을 구한다
   • -
2. 알고리즘을 설계해보자

이 문제는 작은 부분부터 시작하는 것이 더 쉬울 것 같다. (Bottom-up)

 

1. i(0<=i<=9) 에서 부터 시작하여 다음에 올 수 있는 수는 i <= 9

     -> 두 개의 for문을 사용하여 구현할 수 있다.

 

2. 위 조건을 위하여 앞 자리 수를 탐색할 수 있어야 한다.

     -> 앞 자리 수를 메모할 2차원 배열(dp[n+1][10])가 필요하다.

 

3. dp[0][0~9]를 1로 초기화 한다.

 

4. dp[i][j] += dp[i-1][k] 식 사용

 

 

 

 

 

 

 

 

 

 

 

 

 

이를 for문을 이용한 Bottom-down 방식을 이용하여 나타내면,

import java.util.*;

public class B11057 {
    static Integer dp[][];
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int num = input.nextInt();
        dp = new Integer[num+1][10];

        for (int i = 0; i < 10; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < num+1; i++) {
            for (int j = 0; j < 10; j++) {
                dp[i][j] = 0;
                for (int k = j; k < 10; k++) {
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= 10007;
                }
            }
        }

        System.out.println(dp[num][0]%10007);

        input.close();

    }
}

와 같다.

 

 

 

 

tip) nullpointer 오류가 나지 않도록 dp의 0, 1, 2 등의 값을 초기화 해주어야 한다.

tip) 오버플로우가 발생하지 않도록 매번 10,007을 나누어 준다.