[백준 1720] 타일 코드(Java)

문제 링크 : https://www.acmicpc.net/problem/1720

이 문제는 dp 문제입니다. 문제에서 요구하는 점화식을 잘 세운다면 풀 수 있습니다.

우선 각 경우의 수에서 좌우 대칭인 타일 수를 A, 좌우 대칭이 아닌 타일 수를 B라고 했을 때 항상 A+2B의 경우의 수가 나타납니다. 따라서 중복 제거가 된 값인 A+B를 얻기 위해서는 좌우 대칭인 타일 수를 더한 후 절반으로 나누어서 문제를 풀면 됩니다.

그럼 먼저 중복 포함 모든 타일의 경우의 수, 즉 A+2B에 대해 먼저 구해보겠습니다. 각 경우는 크게 2가지입니다.

우선 현재 길이에서 1만큼 뺀 후 1만큼의 길이를 채우는 경우의 수입니다. 이 경우는 1X2 타일 1개를 채우는 경우밖에 없으므로 dp[n-1]과 같습니다.

이어서 현재 길이에서 2만큼 뺀 후 2만큼의 길이를 채우는 경우의 수입니다. 이 경우는 2X1, 2X2 2개의 경우가 존재하므로 dp[n-2]*2가 됩니다.

즉 중복 포함 모든 타일의 경우의 수 dp[n] = dp[n-1] + dp[n-2]*2 가 됩니다.

그럼 각 경우의 중복 타일 수를 체크해보겠습니다. 우선 홀수 번째 경우는 가운데 세로 막대기를 기준으로 대칭인 경우밖에 없습니다. 따라서 가운데 막대기 기준 절반의 길이에 해당하는 dp[n/2] 만큼 더한 후 절반으로 나눠주면 됩니다. 따라서

dp[n] = (dp[n] + dp[n/2])/2

가 됩니다.

짝수 번째 경우는 크게 2가지가 존재합니다. 우선 완벽한 좌우 대칭인 경우입니다. 이 경우는 위와 같이 절반의 길이에 해당하는 dp[n/2]를 더해주면 됩니다. 이어서 가운데에 길이가 2인 블록이 있는 경우입니다. 이는 현재 길이의 절반 만큼에서 1만큼(원래 길이가 2이기 때문에 절반으로 나누면 1로 됩니다) 뺀 길이의 값, 즉 dp[n/2 -1]만큼 더해주면 됩니다. 이 때 2X2, 2X1 2개의 경우가 존재하기 때문에 해당 값을 2배 해서 더해주면 됩니다. 따라서

dp[n] = (dp[n] + dp[n/2] + dp[n/2 -1]*2

가 됩니다.

다음은 코드입니다.

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

public class Main{

    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] dp = new int[31];

        dp[0] = 1;
        dp[1] = 1;

        // 각 경우의 수에서 좌우 대칭인 타일 수를 A, 좌우 대칭이 아닌 타일 수를 B라고 하면
        // 기본적으로 A + 2B 의 경우의 수가 나타난다.
        // 따라서 좌우 대칭인 타일 수를 더해서 반으로 나눠주면 A+B를 구할 수 있다.
        //
        // 중복 포함 모든 타일의 경우의 수
        // 1. 현재 길이에서 2만큼 뺀 후 2만큼 채우는 경우 : 2*2, 2*1 총 2가지 존재 : dp[n-2]*2
        // 2. 현재 길이에서 1만큼 뺀 후 1만큼 채우는 경우 : 1*2 총 1가지 존재 : dp[n-1]
        // dp[n] = dp[n-2]*2 + dp[n-1]
        //
        // 홀수일 경우의 좌우 대칭 타일 수 : 가운데 세로 막대기 기준으로 대칭인 경우밖에 없음
        // 따라서 가운데 막대기 기준 절반의 길이에 해당하는 dp[n/2] 만큼 더한 후 절반으로 나눠주면 됨
        // dp[n] = (dp[n] + dp[n/2])/2
        //
        // 짝수일 경우의 좌우 대칭 타일 수
        // 1. 절반 길이만큼 좌우 대칭 : dp[n/2]
        // 2. 가운데에 길이가 2인 블록이 있는 경우 : 2*2, 2*1 총 2가지 존재
        // 이는 현재 길이의 절반 만큼에서 1만큼 뺀 길이의 값 : dp[n/2 - 1]*2
        // dp[n] = (dp[n] + dp[n/2] + dp[n/2 -1]*2

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

        if(N%2==1) System.out.println((dp[N] + dp[N/2])/2);
        else System.out.println((dp[N] + dp[N/2] + dp[N/2 -1]*2)/2);
    }
}