[백준][15990번] 2xn 타일링

문제 URL

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

나의 풀이

import java.io.*;

public class Main {
    public static final int mod = 1000000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //d[N][L] = 길이가 N인 계단수, 마지막수 L
        int[][] d = new int[n + 1][10];

        //첫번쨰자리수 1로 초기화
        for (int j = 1; j <= 9; j++)
            d[1][j] = 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] %= mod;
            }
        }
        //(1)
        long sum = 0;
        for (int j = 0; j <= 9; j++)
            sum += d[n][j];
        sum %= mod;

        System.out.println(sum);
    }
}

느낀점

동적계획법 을 이용한 문제다.

마지막 (1) 부분에서 오류가 발생했었다. 큰수를 계속 더해서 int 범위를 넘어버린 것이다. 그래서 long형으로 바꿧다. 항상 유의하자!