[JAVA] 백준 1720 - 타일 코드

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

2XN 타일을 각각 1X2, 2X2, 2X1 타일로 채우는 방법의 가짓수를 구하되, 대칭인 경우는 1개로 취급하는 가짓수를 구하는 방법이다.

 

전체 가짓수를 구하고, 대칭인 가짓수를 제외해주면 되는데, 홀수인경우 대칭이려면 가운데 1X2타일을 끼고 대칭인 케이스밖에 없고, 짝수인 경우는 절반이 완전히 대칭인 케이스와 가운데에 2칸을 낀 상태로 나머지 칸들이 대칭인 경우가 있다.

2칸을 채우는 방법은 2X2 혹은 2X1두개를 이용해 채울 수 있다. 1X2두칸은 절반이 완전히 대칭인 케이스에 포함이라 제외했다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = par(br.readLine());
        long[] dp = new long[n+1]; //가능한 전체 가짓수
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <=n ; i++) {
            dp[i] = dp[i-1] + 2*dp[i-2];
        }
        long temp = 0;
        if(n%2==1) temp = dp[n/2]; //가운데 하나를 끼고 n/2짜리가 대칭인 케이스
        else temp = dp[n/2] + 2*dp[n/2-1]; //가운데 없이 n/2가 대칭인 케이스 + 가운데 2X2를 끼고 n/2-1 대칭 + 가운데 가로 2X1 2개를 끼고 n/2 -1 대칭
        System.out.println((dp[n]+temp)/2);
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}