[JAVA] 백준 2133번 : 타일 채우기

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

2133번: 타일 채우기

---

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N + 1];

        dp[0] = 1;
        for (int i = 2; i <= N; i += 2) {
            dp[i] = dp[i-2] * 3;
            if(i == 2) continue;
            for (int j = 0; j < i-2; j+= 2) {
                dp[i] += (dp[j] * 2);
            }
        }
        System.out.println(dp[N]);
    }
}

💡 DP

풀이

• 세로 길이가 3으로 고정되어 있고, 조합 가능한 블록은 2*1, 1*2 존재
• 3*1을 채울 수 있는 방법은 없음, 무조건 3*짝수 단위로 채워야 함 → dp[홀수] = 0
• dp[4]의 경우 dp[2] 에서 3가지 이어붙이는 방법 말고도 가로 길이가 4일때 만의 고유한 배열이 존재함
  • dp[4] = dp[2] * 3 + 2 (고유 배열)
  • 4외에도 6, 8, 10... 모든 경우의 수에 대해 고유한 경우 2가지씩 존재
• dp[6] 의 경우 → 4 + 2 / 2 + 4
  • dp[4] x 3 (dp[2])
  • dp[2] x 2 (= 4칸 고유 배열이 오른쪽에 온 경우) → 얘는 dp[4] * 3에 포함 되지 않음
    • 3 x dp[4] 하기엔 dp[4]에서 고유배열이 아닌 경우의 수가 중복됨.
    • 즉, 고유 배열에 대해서만 왼 / 오 2칸씩 경우의 수 별도로 카운팅 해줘야 함
  • 가로 6칸의 고유 배열 경우의 수 2
  • = 최종 33 + 6 + 2 = 41
• dp[8]의 경우 → 6 + 2 / 4 + 4 / 2 + 6
  • dp[6] x 3
  • dp[4] x 2 (4칸 고유 배열 오른쪽에 온 경우)
    • 마찬가지로 dp[4] x dp[4]로 하면 dp[6] x dp[2]와 중복되므로 고유 배열만 따져준다
  • dp[2] x 2 (6칸 고유 배열 오른쪽에 온 경우)

---

📌 대략 점화식을 아래와 같이 정리해 볼 수 있다.
       dp[i] = dp[i-2] * 3 + dp[i-4] * 2 + dp[i-6] * 2 + ... + dp[2] * 2 + dp[0] * 2 (dp[0] = 1)

 

 

---

 

참고

https://blog.naver.com/hands731/221806277981