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

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

다른 분들의 풀이를 보고 이해한 뒤, 내 방식으로 규칙을 찾은 문제이다.

 

N = 1일 때, 불가능

 

N = 2일 때, 3가지

 

N = 3일 때, 불가능

 

N = 4일 때, 9가지

: dp[2] x dp[2]

: 예외 2가지

 

N = 6일 때, 

: dp[4] x dp[2]

: dp[2] x dp[4]예외(2가지)

: 예외 2가지

 

N = 8일 때,

: dp[6] x dp[2]

: dp[2]  x dp[6]예외(2가지)

: dp[4]  x dp[4]예외(2가지)

: 예외 2가지

 

처음에 헷갈렸던 부분을 N = 6을 예시로 설명하자면

  dp[2]  x dp[4]예외(2가지)

  dp[4]예외(2가지) x dp[2]

위의 두 가지가 있는데 dp[4]예외케이스가 먼저 나오는 경우는 이미  dp[4]  x dp[2]에 포함되어 있는 것이다.

따라서 dp[2]가 먼저 나오고 그 뒤에 dp[4]예외(2가지) 경우가 나오는 케이스를 단순히 더해주기만 하면 됐다.

 

따라서 점화식은 아래와 같다.

---

3. 자바 코드

https://github.com/geujeog/BOJ/blob/main/B2133.java

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

class Main {
    static int N;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        input();
        solution();
        print();
    }

    public static void solution() {
        if (N < 2 || N % 2 == 1) return;

        dp[2] = 3;

        for (int i = 4; i <= N; i+=2) {
            dp[i] = dp[i-2] * dp[2] + 2;

            for (int j = 2; j <= i-4; j+=2) {
                dp[i] += (dp[j] * 2);
            }
        }
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(dp[N]+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new int[N+1];

        br.close();
    }
}

---

4. 결과 및 회고

점화식 너무 어렵다... 더 많이 풀어보면서 비슷한 점화식은 빠르게 찾을 수 있도록 연습해야겠다.