[백준 / 골드4] 2133 타일 채우기 (Java)

문제 보기

사용한 것

• 타일을 채우는 경우의 수를 구하기 위한 bottom-up

풀이 방법

• a 번째 칸의 경우의 수
  • 2칸전의 경우의 수 * 3 (이번꺼 2칸 채우기 -> 3개의 경우 존재)
  • b(4 <= b <= a)칸전의 경우의 수 * 2 (이번꺼 b칸 채우기 -> 특수한 모양 2개 씩 존재)

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1];
        dp[0] = 1;
        if (N >= 2) {
            dp[2] = 3;
        }
        for (int i = 4; i <= N; i += 2) {
            dp[i] = 3 * dp[i - 2];
            for (int j = 4; j <= i; j += 2) {
                dp[i] += 2 * dp[i - j];
            }
        }

        System.out.println(dp[N]);
    }
}