[백준] 동적 프로그래밍 - 11057번 오르막 수 (Java)

문제링크

11057번: 오르막 수

 

접근한 방법

• 동적 프로그래밍

---

풀이방법

아래 문제를 고군분투하며 풀고나니 이 문제는 쉽게 풀 수 있었다.

출처 : 2020/11/29 - [알고리즘/동적 프로그래밍] - [백준] 동적 프로그래밍 - 10844번 쉬운 계단 수 (Java)

 

• 끝자리가 0일 경우 : 앞자리에 0만 올 수 있다. (00)
• 끝자리가 1일 경우 : 앞자리에 0, 1 두가지가 올 수 있다. (01, 11)
• 끝자리가 2일 경우 : 앞자리에 0, 1, 2 세가지가 올 수 있다. (02, 12, 22)
  ....
• 끝자리가 9일 경우 : 앞자리에 0, 1, 2, 3, 4, 5, 6, 7, 8, 9가 올 수 있다. (09, 19, 29, 39, 49, 59, 69, 79, 89, 99)

따라서, 각 자리마다 생각해줘야하므로

배열의 행을 자리수 n

배열의 열을 0~9까지의 경우로 하여 이중 배열로 저장한다.

---

소스코드 작성 방법

• a배열 선언
  행은 1부터 n자리까지를 나타내야하고
  열은 0부터 9까지의 경우를 나타내야하므로
  a[n+1][10]으로 선언
• 자리수 n이 1일 때의 경우 초기화
• 현재의 자리수를 row, 끝자리의 숫자를 col이라고 하여 이중 반복문을 세운다.
  이중 반복문 안에 반복문 하나를 더 선언하여 결과를 구한다.
  구하고자 하는 끝자리 숫자가 col이며 앞자리(row-1)의 끝자리를 i라고 했을 때
  위 풀이 방법에서 알 수 있듯이 i=0 부터 i=col까지의 경우를 더해준다.
  e.g. a[2][3] = a[1][0] + a[1][1] + a[1][2] + a[1][3]
• 마지막으로 10007으로 나눈 나머지를 저장하고,
  각 자리의 경우를 모두 더한 result값에도 10007로 나눈 나머지를 저장한다.

 

소스코드

package baekjoon.dp;
import java.io.*;

public class Q_11057_UphillNum {
    public static long solution(int n){
        long[][] a = new long[n + 1][10];
        
        for (int i = 0; i <= 9; i++) {
            a[1][i] = 1;
        }

        for (int row = 2; row <= n; row++) {
            for (int col = 0; col <= 9; col++) {
                for(int i=0 ; i<=col ; i++)
                    a[row][col] += a[row - 1][i];
                a[row][col] %= 10007;
            }
        }

        long result = 0;
        for (int i = 0; i <= 9; i++) {
            result += a[n][i];
        }
        result %= 10007;

        return result;
    }
    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());
        bw.write(solution(n) +"\n");

        br.close();
        bw.close();
    }
}