[알고리즘 PS] 백준 10844 오르막 수 자바 문제 풀이

문제

해당 포스팅은 백준의 10844번 오르막 수의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

이번 문제는 지난 시간에 배웠던 백준 쉬운 계단 수의 문제와 비슷한 문제이다.

지난 시간에 배웠던 쉬운 계단 수의 문제에서는 n자리에 m 뒤에 올 수 있는 수가 n-1번째의 m + 1번과 m - 1번이었다.

하지만 이번은 조금 다르다.

접근법

 

DP 테이블은 길이가 n자리인 오르막 수에 0 ~ 9가 각각 몇번이 들어가는지 담긴 2차원 배열로 정의할 수 있다.

int[][] dp new int[n+1][10];

arr[n][m] = 10 이라는 DP 테이블이 존재할 때, n은 자리수를 뜻하며(왼쪽에서부터 n의자리 n-1의 자리 ...) m은 n의 자리에 올 수 있는 자연수 (0~9) 를 의미한다.

 

그럼 n+1자리의 m자리를 어떻게 구할까?

 

예를 들어 578이라는 3자리수가 있다고 가정해보자.

5  7  8 이라는 수는

    5             7               8
(n) 번째 수    (n-1) 번째 수    (n-2) 번째 수

과 같이 된다.

 

그럼 x 5 7 8이라는 4자리 수가 있다고 생각하면,

 

x  5  7  8 이라는 수는

     x             5             7               8
(n) 번째 수    (n-1) 번째 수    (n-2) 번째 수    (n-3) 번째 수

위와 같은 형태가 된다.

 

그럼 오르막 수의 특성에 의해서 n 자리에 올 수 있는 수는 n-1번째의 수보다 작은 수여야 한다.

 

그럼 위의 경우, n번째에 올 수 있는 수는

• 5 - 0 = 5;
• 5 - 1 = 4;
• 5 - 2 = 3;
• 5 - 3 = 2;
• 5 - 4 = 1;
• 5 - 5 = 0;

으로 총 6개의 수가 올 수 있다.

 

그럼

• 0578 이 될 때의 경우의 수 (578의 경우의 수)
• 1578 이 될 떄의 경우의 수 (578의 경우의 수)
• 2578 이 될 때의 경우의 수 (578의 경우의 수)
• ...
• 5578 이 될 떄의 경우의 수 (578의 경우의 수)

이 되므로 578의 경우의 수를 오르막수에 해당하는 수가 될 때 까지 합산해주면 된다.

int[][] dp new int[n+1][10];

정답 코드

import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int n = Integer.parseInt(br.readLine());

    int[][] dp = new int[1001][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++){
        int sum = 0;
        for(int k = 0; k <= j; k++) {
          sum = (sum + dp[i-1][k]) % 10007;
        }
        dp[i][j] = sum % 10007;
      }
    }

    int answer = 0;
    for(int i = 0; i < dp[n].length; i++) {
      answer = (answer + dp[n][i]) % 10007;
    }

    bw.write(String.valueOf(answer));
    bw.flush();
    bw.close();
  }
}

---

문제 회고

이 문제는 쉬운 계단 수와 유사한 느낌의 문제라는 것을 문제를 읽다가 알게 되었다.
그리고 쉬운 계단 수를 풀고 바로 풀었던 문제이다. 쉬운 계단 수도 누군가의 답을 보고 풀었던 문제였었다.
쉬운 계단 수에서 적용하단 방식이 이미 내 머리속에 각인되어 있었기 때문에 나는 해당 문제에서 새로운 생각을 할 여유가 없었다.
아마 쉬운 계단 수의 규칙만 보고 지난 문제를 넘어갔기 때문이 아닐까 싶다.
아직 부족한 것은 확실하겠지만, 한 문제를 풀고 회고를 하며 다양한 접근을 해보는 것이 중요하다고 느낀 문제이다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.