BOJ 1720 - 타일 코드

문제

2 X N 사각형을 2 X 1, 2 X 2 타일으로 채우는 경우의 수를 구해야 한다.
이때 좌우 대칭인 두 가지 결과가 존재할 경우 둘을 하나로 처리한다.

풀이

전체 타일의 경우의 수에 대한 점화식은 아래와 같다.
dp(n)=2*dp(n-2)+dp(n-1)

이때 팰린드롬 형태인 결과물은 좌우 대칭이 되는 결과물이 없고, 나머지 결과물들은 모두 좌우 대칭인 짝이 존재한다.
따라서 (전체 경우의 수 - 팰린드롬의 수)/2 + 팰린드롬의 수가 해답이다.

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        long t;
        long[] dp = new long[n];
        dp[0] = 1;
        if(n>1) dp[1] = 3;
        if(n<3){
            System.out.println(dp[n - 1]);
            return;
        }
        for (int i = 2; i < n; i++) dp[i] = 2 * dp[i - 2] + dp[i - 1];
        if (n % 2 == 0){
            t = 2 * dp[(n - 1) / 2 - 1] + dp[(n - 1) / 2];
        } else t = dp[(n - 1) / 2 - 1];
        dp[n - 1] = (dp[n - 1] - t) / 2 + t;
        System.out.println(dp[n - 1]);
    }
}

풀고나서

• 팰린드롬인 경우를 제외한 모든 경우는 대칭이라는 사실을 깨닫는게 시간이 걸렸다.