[백준] Silver I. 쉬운 계단 수

https://www.acmicpc.net/problem/10844

 

사용 알고리즘

• 다이나믹 프로그래밍

 

풀이

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

/*
    테이블: d[i][j]: 길이가 i이고 마지막 숫자가 j일때 가질 수 있는 모든 경우의 수
    점화식:
        * d[i][j] = d[i-1][j-1] + d[i-1][j+1], 단 j-1>0, j+1<10
 */
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        int [][] d = new int[n+1][10];

        for(int i = 1; i <= 9; i++) { // 초기화.
            d[1][i] = 1;
        }

        for(int i = 2; i <= n; i++) {
            for(int j = 0; j <= 9; j++) {
                if (j == 0) d[i][j] += d[i-1][j+1];
                else if (j == 9) d[i][j] += d[i-1][j-1];
                else d[i][j] = d[i-1][j-1] + d[i-1][j+1];
                d[i][j] %= 1000000000;
            }
        }

        int sum = 0;
        for(int i = 0; i <= 9; i++) {
            sum += d[n][i];
            sum %= 1000000000;
        }
        System.out.println(sum);
    }
}

 

 

회고

 

이전에 못풀고 답안을 참고했던 문제인데 다시 풀어서 맞췄다!

 

테이블: d[i][j]: 길이가 i이고 마지막 숫자가 j일때 가질 수 있는 모든 경우의 수
점화식: d[i][j] = d[i-1][j-1] + d[i-1][j+1], 단 j-1>0, j+1<10

 

일단 테이블과 점화식은 이렇게 된다.

 

길이가 1이고 마지막 숫자가 2일때 가짓 수는 2개고, 길이가 2고 마지막 숫자가 2일때를 생각해보면 12,32 두가지 케이스가 있다.

 

12 -> 마지막 숫자가 1일 때 + 2

32 -> 마지막 숫자가 3일 때 + 2

 

이렇게 해서 두가지 케이스가 존재한다.

 

그렇기 때문에, d[i][j] = d[i-1][j-1] + d[i-1][j+1]이라는 식이 성립을 한다! 

 

단, j-1이 음수가 되거나 j+1이 9보다 클 때 엣지 케이스가 있으므로 이부분을 염두해서 풀이를 해야한다. 안그러면 indexOutofBounds 에러뜸