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

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

 

문제 출처

www.acmicpc.net/problem/2133

2133번: 타일 채우기

---

※ 풀이

이 문제 또한 2xn 타일 채우기와 유사한 문제이지만 

높이가 3으로 늘어나서 난이도가 높아진 문제이다.

 

마찬가지로 동적계획법(DP)을 이용하여 점화식을 세워 풀어나가면 되지만

점화식을 세우는 과정에 생각해봐야 할 부분이 많다...

 

먼저 이 문제의 경우 홀수가 주어질 경우 타일을 끼워맞출 수 없다.

때문에 주어진 값이 홀수일 경우 계산하지 않고 0을 반환하도록 하였다.

 

짝수인 경우에는 다음과 같이 추론해볼 수 있다.

 

a[2]=3

a[4]=11

...

a[n]=3 * a[n-2] + (a[n-4] * 2 + a[n-6] * 2+ ...  + a[0])

 

조금 독특한 형태의 점화식을 띄고 있는데

단순하게 생각하면 그 전 블럭(a[n-2]) 항보다 다음 항(a[n])이 될 때 생기는 모양이

3개가 있으니 3배를 하면 되겠다고 생각해서 좋다고 코드만들어서 제출하면 답이 틀리다고 나온다.(필자의 경우이다....ㅠㅠ)

 

그 이유는 함정이 있어서 인데

그 전전항 a[n-4] 에서 a[n] 이 될 때 비로소 생길 수 있는 블록의 모양이 2개 존재하기 때문이다...

 

때문에 a[n-4] 부터 a[0] 까지 쭉 더하는 형태로 코드를 추가해주어야 한다.

 

 

---

※ 주의할 점

아래 소스코드에서 idx==0 인 경우를 왜 추가하였는지 궁금할 수 있는데

단순하게 n=4 인 경우를 계산해보면 그 이유를 알 수 있다.

 

이걸 적어주지 않으면 a[0] 값, 즉 n=4 일때 값까지 카운트해줄 수 없기 때문이다.

---

※ 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    static long[] arr = new long[31];

    public static void main(String[] args) throws IOException {
        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if (n % 2 == 1) {
            System.out.println(0);
            return;
        }

        Arrays.fill(arr, -1);

        System.out.println(dynamic(n));
    }

    static long dynamic(int idx) {
        if (idx == 2) return 3;
        else if(idx==0) return 1;
        else if (arr[idx] != -1) {
            return arr[idx];
        } else {
            long a = 3 * dynamic(idx - 2);

            long sum = 0;
            for (int i = idx - 4; i >= 0; i -= 2) {
                sum += 2 * dynamic(i);
            }

            return arr[idx] = (a + sum);
        }
    }
}