문제 링크

성능 요약

메모리: 14212 KB, 시간: 104 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 29일 17:45:24

문제 설명

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

풀이

느낀점

• 알듯말듯 너무 어려웠다..
• 수를 하나씩 늘려가면서 규칙을 찾으려고 했지만, 다 알고보면 거의 다 왔는데 그 규칙 정리하지 못했다.ㅠㅠ
• 참고해도 이해하는데 조금 걸렸다.

설계 : 90분 - 참고

• 입력된 수가 짝수일 때만 경우의 수가 존재한다.
• n=2일때, 경우의 수는 3이다.
• n=4일때, n-2의 전체 경우의 수에 뒤에 2칸이 연장되므로 3을 곱한다.
• 단, 2이상의 길이에서는 모두 각 수마다 특이한 타일 모양이 2개씩 생성된다.
• 따라서 n=4일때는 3*3+2 = 11
• n=6일때, 11*3+2을 우선하고나면 의문이 생긴다.
• n-2에서 2를 연장한 경우 외에 n-4, n-6, n-8…(n>0인 경우 까지만)에서 각각 길이 4인 특이 케이스, 길이 6인 특이 케이스 등을 더하는 경우는 11*3+2에 포함되지 않는다.
• 초기 계산에 포함된 경우의 수에는 각각의 특이케이스가 왼쪽에 포함되는 경우 뿐으로, 오른쪽 끝에 추가되는 경우만 빠져있다. 따라서 특이케이스가 생기는 길이 4부터 오른쪽에 붙는 경우를 모두 더해줘야 한다.

코드(Java)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 타일 채우기_2133
 * Date: 2025.01.28
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
		if (n % 2 != 0) {
			bw.write("0");
		} else {
			long[] dp = new long[n+1];
			dp[2] = 3;
			for (int i = 4; i <= n; i += 2) {
				dp[i] = (dp[i-2] * 3) + 2;
				for (int j = i-4; j > 0; j--) {
					dp[i] += dp[j] * 2;
				}
			}

			bw.write(String.valueOf(dp[n]));
		}
		bw.flush();
		bw.close();
		br.close();
	}
}