BOJ 백준온라인져지 2133 타일 채우기 풀이

문제 설명 및 풀이

1. 3 * 2 일 때 만들 수 있는 경우 3 가지

2. 3 * 4 부터 2 * 2 를 추가할 수 있다. 그래서 2 가지 더해주고

3. 3 * 6 일 때 또 패턴 생기고 쭉 생김

증명

솔직히 증명은 못하겠다. (다른 블로그들을 참고했기 때문이다.)

1. 비트마스크로 구하고 DP 하는 방법도 있다한다. 그건 증명이 가능할듯

코드

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/2133
	* BOJ 백준온라인져지 2133 타일 채우기 풀이
	*/
	public class Main {
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	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 + 2];
	dp[0] = 1;
	dp[2] = 3;
	for (int i = 4; i <= N; i += 2) {
	dp[i] = dp[i - 2] * 3;
	for (int j = 4; j <= i; j += 2) {
	dp[i] += dp[i - j] * 2;
	}
	}
	bw.write(String.valueOf(dp[N]));
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

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

입력

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

출력

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

예제 입력 1 

2

예제 출력 1 

3

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

출처

Contest > Waterloo's local Programming Contests > 24 September, 2005 D번