21.07.23 - [BOJ] 2133. 타일 채우기

[suhyunsim]

문제

• 2133

핵심 아이디어

• D[i] = 3 * D[i-2] + 2D[i-4] + 2D[i-6] + …

어려운 점, 실수

• 더 구할 수 있는 방법에 대해 아이디어가 떠오르지 않았다.

풀이

package main.java.com.poogle.BOJ.Q2133;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] d = new long[n + 1];
        d[0] = 1;
        for (int i = 2; i <= n; i += 2) {
            d[i] = d[i - 2] * 3;
            for (int j = i - 4; j >= 0; j -= 2) {
                d[i] += d[j] * 2;
            }
        }
        System.out.println(d[n]);
    }
}