백준 2133번 타일 채우기 JAVA

링크텍스트

설명

풀이 흐름 설명

작은 값부터 직접 계산해 보며 규칙을 찾기로 했다.
3×1은 채울 수 없으므로 0이다.
3×2는 3가지이다.
3×3은 다시 채울 수 없으므로 0이다.
이를 통해 N이 홀수이면 경우의 수는 0이라는 사실을 먼저 정리하였다.
따라서 이후에는 N이 짝수일 때만 고려하면 되었다.

다음으로 3×4를 직접 그려보았다.
처음에는 단순히 3×2의 경우(3가지)를 두 번 붙이면 9가지일 것이라고 생각하였다.
하지만 직접 그려보니 기본 배치 외에 특수한 모양이 2가지 더 존재한다는 것을 알게 되었다.
그래서 3×4의 정답은 11이 된다.
이 특수한 2가지 모양 때문에 점화식이 단순하지 않다는 것을 깨달았다.

점화식에 대한 고민과 해결

먼저 dp[2] = 3으로 초기화하였다.
이후 dp[4]를 계산하는 과정에서 다음과 같은 규칙을 발견하였다.
기본적으로는 오른쪽 끝 2칸을 채우는 방법이 3가지 존재한다.
따라서 왼쪽 공간을 채우는 경우의 수 dp[i-2]에 3을 곱하면 기본 구조는 모두 포함할 수 있다.

dp[i] = dp[i-2] * 3이 된다.

하지만 여기에는 3×4에서 확인했던 특수한 2가지 모양이 포함되지 않는다.
이 특수한 모양은 단순히 오른쪽 2칸만 보는 것으로는 만들 수 없고
가로 방향으로 길게 이어지는 구조에서 발생한다.
그래서 i-4, i-6, … 처럼 더 왼쪽까지 확장된 경우들을 모두 고려해야 한다는 것을 알게 되었다.
이를 코드로 구현하면 다음과 같은 형태가 된다.

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

여기서 dp[j] * 2는 왼쪽에 j칸을 채우고 나머지 오른쪽 부분을 특수 모양 2가지 중 하나로 채우는 경우를 의미한다.
이 과정을 통해 모든 특수한 연결 형태를 누적해서 계산할 수 있었다.

dp[i] += 2에 대한 이해

일부 구현에서는 반복문에서 j > 0까지만 돌리고 마지막에 dp[i] += 2를 추가하는 방식도 있다.
이는 dp[0]을 따로 사용하지 않고
가장 왼쪽이 전부 특수 모양으로 채워지는 2가지 경우를 직접 더해주는 방식이다.

dp[0] = 1을 두고 반복문에서 포함시키거나
dp[0]을 사용하지 않고 마지막에 +2를 하거나
본질은 동일하며 구현 방식의 차이일 뿐이다.

더 최적화할 수 있는 방법

위 점화식을 정리하면 다음과 같은 더 간단한 점화식으로 변형할 수 있다.

dp[i] = 4 * dp[i-2] - dp[i-4]

이 점화식을 사용하면 내부 반복문이 필요 없어지고
시간 복잡도를 O(N)으로 줄일 수 있다.
기본 아이디어는 누적 합 기반 점화식
수학적으로 정리하면 선형 점화식이라는 흐름으로 이해할 수 있었다.

정리

이 문제는 처음에는 단순한 곱셈 문제처럼 보였지만
3×4에서 등장하는 특수한 2가지 모양 때문에 점화식이 복잡해지는 문제였다.
N이 홀수이면 정답은 0이다.
기본 구조는 dp[i-2] * 3이다.
특수 모양을 누적해서 더해주어야 한다.
수학적으로 정리하면 O(N) 점화식으로 최적화할 수 있다.
작은 예제를 직접 그려보는 것이 가장 중요했던 문제였다.
시간복잡도: O(N²), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        if(n<2 || n%2!=0){
            System.out.println(0);
            return;
        }

        int [] dp = new int[n+1];

        dp[2] = 3;

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

        System.out.println(dp[n]);

        // i=2 3*2 = 2+1 = 3개
        // i=4 11개
        // i=6 41개
    }
}