Baekjoon 11057 오르막 수 JAVA

11057번: 오르막 수

문제

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

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

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

 

조건

[입력]

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

 

[출력]

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

 

풀이

해당 문제는 자릿 수가 주어질 때 해당 자릿수의 숫자로 만들 수 있는 오름 차수 수를 구하는 문제다.

단 0으로 시작할 수 있고, 000 ,11 도 오름차순 숫자로 친다.

 

해당 문제는 dp를 이용하여 각각 경우의 수를 2차원 배열에 저장하는 방식으로 해결하였다.

 

2차원 배열의 [i][j]라고 치면 i는 숫자의 자릿수를 나타내고 j는 숫자의 시작 숫자를 나타낸다.

 

로직은 다음과 같다.

먼저 한 자릿수에 대해서 모두 1로 초기화를 해준다.

이후 두 자릿수부터 갱신을 해주는데 예를 들어 두 자리 숫자에 대해서 0부터 시작할 경우 가능한 수는 00,01... 09 총 10개다.

1부터 시작할 경우는 11, 12... 19까지 총 9개다.

이를 dp를 이용하여 해결하면 [2][0]의 경우 [1][0] ~ [1][9]까지의 모든 합을 더한 게 경우의 수가 되는 셈이다.

이를 코드로 나타내면 dp [i][j] += dp [i-1][k]가 되며 3중 포문을 이용하여 2차원 배열을 전체 탐색하고 k는 j부터 10까지 증가하며 더하는 방식으로 코드를 구현하면 된다.

문제에서 10007로 나눈 나머지를 출력하라고 하였기에 더하면서 계속 나눠주고 최종 출력에서도 나눠주면 해결 가능하다.

 

코드

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

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int dp[][] = new int[N+1][10];

        for (int i = 0; i < 10; i++) { // 처음 한자리수는 경우의수가 각각 하나임
            dp[1][i] = 1;
        }

        for (int i = 2; i <= N; i++) { // 두자리수부터 갱신을 해준다.
            for (int j = 0; j < 10; j++) {
                for (int k = j; k < 10; k++) { // i 는 자리수 j 는 시작하는 수
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= 10007;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < 10; i++) {
            ans += dp[N][i];
        }
        System.out.println(ans%10007);
    }
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드