백준 11057: 오르막 수 - DP 동적프로그래밍 (파이썬, 자바)

오르막 수 성공 

11057번: 오르막 수

문제

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

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

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

입력

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

출력

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

 

내 코드

import sys
n=int(sys.stdin.readline())

now=[1,1,1,1,1,1,1,1,1,1] #초기값

for i in range(n-1):
    before=now[:] #이전 값을 복사
    for j in range(10):
        now[j]=sum(before[j:]) #j로 시작하는 n자리 오르막 수: sum(j~10 으로 시작하는 n-1자리 오르막 수)

print(sum(now)%10007)

 

풀이 및 접근)

 

- 어느 한 자리를 고정하고 생각해야 일반화를 할 수 있을거라 생각했다. 그래서 맨 앞자리를 고정하고 생각해보았다.

- 3자리를 기준으로 예를 들어보면, 0으로 시작하는 3자리 오르막 수는, 0으로 시작하는 2자리 오르막 수 + 1로 시작하는 2자리 오르막 수 + . . . 9로 시작하는 오르막 수 이다. 또, 1로 시작하는 3자리 오르막 수는, 1로 시작하는 2자리 오르막 수 + 2로 시작하는 오르막 수 + . . .

. . .

- 규칙을 찾을 수 있을 것이다. k로 시작하는 n자리 오르막 수는, k to 9로 시작하는 n-1 자리 오르막 수들의 합이다. 이를 활용하여 일반화 할 수 있다.

- 코드에서는 계속 배열을 만들어 나가지 않고, 초기의 1차원 배열 하나만을 이용해서 복사한 뒤 그것을 통해 배열을 최신화 시키는 방식으로 구했다.

- 많은 풀이들에서, 세로 축에는 자리 수, 가로 축에는 끝자리 수의 표를 그려서 표 상에서 규칙이 도출되는 것으로 계산을 하는데, 이것보다 필자의 논리적인 접근을 통한 풀이가 더 쉽다고 생각한다.

 

자바 ver.

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

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

        int[]now={1,1,1,1,1,1,1,1,1,1};


        for(int i=0; i<n-1; i++){
            before=Arrays.copyOf(now,10);
            for(int j=0; j<10; j++){
                int tmp=0;
                for(int k=j; k<10; k++){
                    tmp+=before[k]%10007;
                }
                now[j]=tmp;
            }
        }

        int answer=0;
        for (int i : now) {
            answer+=i;
        }
        System.out.println(answer%10007);
    }
}

 

- 자바는 연산 과정에서 오버플로우가 발생하므로, 값을 넣을 때마다 %10007을 미리미리 해두어야 한다. 그래야 오버플로우가 나지 않는다.

- 나머지 연산은, 어떤 과정에서 먼저 이루어져도 그 값은 항상 같다.