[DP] 타일링 DP (백준 2302)

목차

• 1. 서론: 복잡해 보이는 문제, 단순하게 바라보기
• 2. 왜 ‘위치 추적(dp[n][3])’은 실패하는가?
• 3. 점화식 유도: 마지막 사람에게 집중하라
• 4. VIP 좌석: 문제를 쪼개는 마법의 가위
• 5. 이 유형의 절대 공식: 4단계 구현법
• 6. 최종 구현 및 코드 정밀 분석
• 7. 결론: 타일링 DP의 확장

1. 서론: 복잡해 보이는 문제, 단순하게 바라보기

코딩 테스트에서 ‘경우의 수’를 묻는 문제가 나오면 많은 지원자가 당황합니다. 특히 백준 2302번처럼 “자리를 바꿀 수 있는데, 양옆으로만 가능하고, VIP는 고정이다” 같은 조건이 붙으면 머릿속으로 시뮬레이션을 돌리다가 꼬이기 십상입니다.

하지만 이 문제는 복잡한 조건들을 걷어내면, 우리가 수학 시간에 배웠던 ‘피보나치 수열’과 100% 일치합니다. 이번 리포트에서는 문제를 있는 그대로 구현하려다 늪에 빠지는 ‘시뮬레이션의 함정’을 분석하고, 이를 타일링(Tiling) DP 관점으로 치환하여 아주 우아하게 해결하는 방법을 소개합니다.

2. 왜 ‘위치 추적(dp[n][3])’은 실패하는가?

우선 N번 사람이 x-1, x, x+1 위치에 앉는 경우(dp[n][3])를 생각해 문제를 풀고자 했다면, 직관적인 접근처럼 보이지만 치명적인 논리적 결함이 있습니다.

함정: 상호 의존성 (Mutual Dependency)

이 문제에서 자리를 바꾼다는 것은 “나 혼자 이동하는 것”이 아니라 “상대방과 교환(Swap)하는 것”입니다. 즉, 내가 자리를 옮기면 상대방의 위치도 강제로 결정됩니다.

• 만약 N번 사람이 N-1번 자리로 이동했다고 가정해 봅시다.
• 그러면 N-1번 사람은 선택권이 없습니다. 무조건 N번 자리로 와야 합니다.
• 하지만 dp[n][3] 방식은 N번 사람의 위치만 기록할 뿐, 그로 인해 영향을 받은 N-1번 사람의 상태나, 그 이전 사람들의 연쇄적인 이동 가능성을 깔끔하게 끊어내지 못합니다.

결국 “누가 어디에 앉았냐”를 추적하려면, 현재 사람뿐만 아니라 아직 배치되지 않은 사람들의 상태까지 고려해야 하므로 상태 공간이 기하급수적으로 늘어납니다. DP의 핵심은 ‘과거의 결정이 미래의 선택지를 제한하지 않아야 한다(무기억성)’는 것인데, 위치 추적 방식은 이 원칙을 위배하게 됩니다.

3. 점화식 유도: 마지막 사람에게 집중하라

복잡한 관계를 끊어내는 열쇠는 “가장 마지막 사람(N)의 선택”만 보는 것입니다. N개의 좌석이 있을 때, N번 회원이 취할 수 있는 행동은 딱 두 가지뿐입니다.

Case 1: 제자리에 앉기 (Stay)

N번 회원이 N번 좌석에 앉습니다. 아주 심플합니다. 이 경우, 남은 문제는 N-1명의 회원을 배치하는 문제와 같아집니다.

경우의 수: dp[N-1]

Case 2: 왼쪽 사람과 바꾸기 (Swap)

N번 회원이 N-1번 좌석에 앉습니다. 이때 N-1번 회원은 자동으로 N번 좌석으로 튕겨갑니다. 두 명(N, N-1)의 자리가 확정되었습니다. 남은 문제는 N-2명의 회원을 배치하는 문제가 됩니다.

경우의 수: dp[N-2]

점화식의 탄생

오른쪽(N+1)은 좌석이 없으므로 고려할 필요가 없습니다. 따라서 N명을 배치하는 경우의 수는 위 두 가지 케이스의 합입니다.

4. VIP 좌석: 문제를 쪼개는 마법의 가위

이제 ‘VIP 좌석’ 조건을 처리해야 합니다. VIP 좌석은 “절대 움직일 수 없는 고정석”입니다. 이는 곧 벽(Wall)과 같습니다.

만약 9개의 좌석 중 4번, 7번이 VIP라면?

[1, 2, 3]  (VIP:4)  [5, 6]  (VIP:7)  [8, 9]

VIP 회원은 자리를 바꿀 수 없으므로, 1~3번 그룹은 5~6번 그룹과 섞일 수 없습니다. 즉, 하나의 큰 문제가 세 개의 작은 독립적인 문제로 쪼개집니다.

1. 길이 3인 좌석 배치 경우의 수 (dp[3])
2. 길이 2인 좌석 배치 경우의 수 (dp[2])
3. 길이 2인 좌석 배치 경우의 수 (dp[2])

각 사건은 독립적으로 일어나므로, 곱의 법칙을 적용하여 dp[3] * dp[2] * dp[2]가 최종 정답이 됩니다.

5. 이 유형의 절대 공식: 4단계 구현법

이러한 유형(분할 가능한 선형 DP)을 만났을 때, 고민 없이 코드를 작성할 수 있는 4단계 순서입니다.

Step 1: DP 테이블 전처리 (Pre-calculation)

N이 최대 40으로 매우 작습니다. 입력값에 따라 매번 계산하지 말고, 피보나치 수열을 미리 40번까지 꽉 채워둡니다.

Step 2: VIP 입력 및 정렬

VIP 좌석 번호를 입력받습니다. (이 문제에서는 오름차순으로 주어지지만, 만약 아니라면 정렬이 필요합니다.)

Step 3: 구간 분할 (Segmenting)

반복문을 돌며 VIP와 VIP 사이의 거리(좌석 개수)를 구합니다. 이 ‘거리’가 곧 DP 테이블의 인덱스가 됩니다.

Step 4: 누적 곱 (Multiply)

각 구간의 DP 값을 결과 변수(ans)에 계속 곱해줍니다. 주의할 점은 마지막 VIP 이후부터 끝 좌석(N)까지의 구간을 빼먹지 않는 것입니다.

6. 최종 구현 및 코드 정밀 분석

위의 4단계 공식을 그대로 옮긴 Java 코드입니다. Scanner보다 빠른 BufferedReader를 사용한 정석 패턴입니다.

import java.io.*;

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()); // 전체 좌석 수
        int M = Integer.parseInt(br.readLine()); // VIP 좌석 수

        // [Step 1] DP 테이블 전처리 (피보나치)
        // dp[i]: 연속된 i개의 좌석을 배치하는 경우의 수
        int[] dp = new int[41];
        dp[0] = 1; // 좌석이 0개(VIP끼리 붙어있음)일 때 곱셈에 영향 없도록 1 설정
        dp[1] = 1; // 좌석 1개: 경우의 수 1 (제자리)
        dp[2] = 2; // 좌석 2개: 경우의 수 2 (제자리, 스왑)

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

        // [Step 2, 3, 4] VIP 기준으로 구간 나누어 곱하기
        int totalWays = 1; // 결과값 (곱셈 항등원 1로 초기화)
        int lastVipIndex = 0; // 이전 VIP 위치 (초기값: 0번 좌석이 VIP라고 가정)

        for (int i = 0; i < M; i++) {
            int currentVip = Integer.parseInt(br.readLine());
            
            // 구간의 길이 = 현재 VIP - 이전 VIP - 1
            // 예: 1 2 3 (4) -> 4 - 0 - 1 = 3칸
            int count = currentVip - lastVipIndex - 1;
            
            totalWays *= dp[count]; // 구간의 경우의 수를 곱함
            lastVipIndex = currentVip; // 기준점 갱신
        }

        // [중요] 마지막 VIP 이후 ~ 끝(N)까지 남은 구간 처리
        // 예: ... (7) 8 9 (N=9) -> 9 - 7 = 2칸
        int remain = N - lastVipIndex;
        totalWays *= dp[remain];

        System.out.println(totalWays);
    }
}

7. 결론: 타일링 DP의 확장

백준 2302번 문제는 “어렵게 생각하면 한없이 어렵고, 단순하게 보면 한없이 단순한” DP의 이중성을 잘 보여줍니다. dp[n][3]처럼 모든 상태를 시뮬레이션하려는 유혹을 뿌리치고, 문제의 본질인 ‘마지막 사람의 선택지’에 집중했을 때 비로소 피보나치라는 단순한 규칙이 보입니다.

또한, VIP라는 요소를 ‘장애물’이 아닌 ‘문제 분할자(Divider)’로 인식하는 사고방식은 추후 더 복잡한 분할 정복(Divide and Conquer) 문제를 풀 때도 큰 자산이 될 것입니다. 이제 좌석 배치 문제가 나오면 당황하지 말고 외치세요. “이건 그냥 피보나치잖아!”