[ 백준 / 자바 ] 2133. 타일채우기

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

2133번: 타일 채우기

---

---

📑 문제

3N 크기의 벽을 21, 1*2 크기의 타일로 채우는 경우의 수를 구하는 문제

 

💡 입력

✔ 첫째 줄에 N 제시

✔ 1 ≤ N ≤ 30

 

 

---

---

✨ 풀이과정

✔ memoization 활용

✔ N이 짝수일 경우에만 타일 채우기 가능

✔ 점화식 발견

 

💥 N = 4일 때, memo[4] = memo[2]*3 + 2로 memo[n] = memo[n-2]*3 + 2 라고 생각할 수 있지만

N=6부터 예외 발생

💥 memo[8] = memo[6]*3 + memo[4]*2 + meeoo[2]*2 + memo[0]*2

따라서 n-2는 *3을 해주되, n-4부터 n-n이 될때까지 각각의 값에 *2를 해주는 수열을 처리해야 함

 

---

---

📑 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static long ans;
	static int[] memo;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		memo = new int[N + 1];
		Arrays.fill(memo, -1); //초기값은 -1로 세팅
		int ans = 0;
		if(N%2==0) ans = solve(N); //짝수일 경우에만 점화식으로 ans 갱신

		System.out.println(ans);

	} // main

	private static int solve(int n) {

		memo[0] = 1;
		memo[2] = 3;

		if (n >= 4) {
			for (int i = 4; i <= n; i += 2) {
				memo[i] = memo[i-2] * 3;
				for(int j=i-4; j>=0; j-=2) { //수열
					memo[i] += (memo[j]*2); //마지막에 memo[0]*2 = 2로 예외경우가 생기는 2를 더해주는 것
				}
//				System.out.println("i: "+i+"\\n"+memo[i]);
			}
		}

		return memo[n];
	}

}