[백준] 동적 프로그래밍 - 10844번 쉬운 계단 수 (Java)

문제링크

10844번: 쉬운 계단 수

접근한 방법

• 동적 프로그래밍

---

풀이 방법

n=4일 때까지, 전부 나열해보고 규칙을 찾아보려 했지만 전혀 보이지 않았다.

앞자리가 0, 9일 때 다음 자릿수에 올 수 있는 건 한가지뿐이어서

각 n자리수마다 0과 9의 갯수를 세서 규칙을 찾아보려했지만, 발견하지 못했다.

 

그래서 다른 블로그들의 글을 보고.. 해결하였다.

 

• 끝자리가 0일 경우 : 앞자리에 숫자 1만 가능하다. (한가지) 
• 끝자리가 1~8일 경우 : 끝자리를 i라고 한다면 앞자리에 숫자 i-1, 숫자 i+1 이 가능하다. (두가지)
  e.g. 끝자리가 1이라면 앞자리에 0, 2가 가능하다.
• 끝자리가 9일 경우 : 앞자리에 숫자 8만 가능하다. (한가지)

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

배열의 행을 자리수 n

배열의 열을 0~9까지의 경우로 하여 이중 배열로 저장하는 것이 포인트였다.

(이중 배열 상상도 못함 T^T)

---

소스코드 작성 방법

• a배열 선언
  숫자가 int 범위를 벗어나게끔 커지므로, long으로 선언
  행은 1부터 n자리까지를 나타내야하고
  열은 0부터 9까지의 경우를 나타내야하므로
  a[n+1][10]으로 선언
• 자리수 n이 1일 때의 경우 초기화
• 끝자리의 경우가 0, 9, 1~8을 나누어서 조건문을 세움
  현재의 자리수를 row, 끝자리의 숫자를 col이라고 한다면,
  row-1의 경우에 따라 뒷자리에 붙을 수 있는 개수가 정해지므로
  
  • 0일 경우, 앞자리에 1만 올 수 있다.
    따라서, a[row][col] = a[row-1][col+1] (a[row-1][1]로 해도 무방)
    e.g. a[2][0] = a[1][1] = 1  (10 으로 한가지)
  • 9일 경우, 앞자리에 8만 올 수 있다.
    따라서, a[row][col] = a[row-1][col-1] (a[row-1][8]로 해도 무방)
    e.g. a[2][9] = a[1][8] = 1 (89 로 한가지)
  • 1~8일 경우, 앞자리에 col-1과 col+1 두가지 경우가 올 수 있다.
    따라서, a[row][col] = a[row-1][col-1] + a[row-1][col+1]
    e.g. a[2][1] = a[1][0] + a[1][2] = 0 + 1 = 1 ( 01 21 (01은 불가능한 숫자) 로 한가지)
• 위 조건에 따라 a[row][col]을 구한 후 1000000000 나머지를 연산해 저장한다.
• 마지막 포인트는, row가 n일 때의 0~9자리를 다 더한 뒤에도 1000000000의 나머지를 연산해 저장한다.

 

소스코드

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

public class Q_10844_EasyStair {
    public static long solution(int n) {
        long[][] a  = new long[n+1][10];

        // n이 1일 때 1로 초기화
        for (int col = 1; col <= 9; col++) {
            a[1][col] = 1;
        }

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

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

        result %= 1000000000;

        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();
    }
}