[Algorithm] C++ 백준 17682번 Tents

문제 요약

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

JOI-kun이 운영하는 캠핑장이 H×W 격자로 나뉘어 있습니다. 각 칸에 최대 하나의 텐트를 배치할 수 있으며, 각 텐트는 4방향(N, S, E, W) 중 하나를 향해야 합니다.

제약조건:

같은 열의 두 텐트는 위쪽이 남(S), 아래쪽이 북(N)을 향함
같은 행의 두 텐트는 왼쪽이 동(E), 오른쪽이 서(W)를 향함
최소 1개 이상의 텐트 배치

요구사항: 조건을 만족하는 모든 배치 방법의 수를 mod 10^9+7로 출력

입출력

입력:

1
H W

출력:

1
경우의 수 mod 1000000007

예제:

1
2
3
4
5
입력: 1 2
출력: 9

입력: 4 3
출력: 3252

접근 개요

핵심 관찰

텐트의 분류: 텐트들을 3가지 타입으로 분류
- Row-pair: 같은 행에 있는 2개의 텐트 쌍 (방향 고정: E, W)
- Column-pair: 같은 열에 있는 2개의 텐트 쌍 (방향 고정: S, N)
- Isolated: 혼자 있는 텐트 (방향 4가지 선택 가능)
독립성:
- Row-pair가 사용하는 행들은 column-pair에 사용 불가
- Column-pair가 사용하는 열들은 row-pair에 사용 불가
- Isolated 텐트들은 각 행/열에 최대 1개씩만 배치 가능

상태 정의

r = row-pair의 개수 (사용 행: 2r)
c = column-pair의 개수 (사용 열: 2c)
Isolated 영역: (H-r-2c) × (W-c-2r) 격자

계산 방식

각 (r, c) 쌍에 대해:

H개 행 중 r개 선택: C(H, r)
W개 열 중 c개 선택: C(W, c)
Row-pair: (W-c)개 열에서 2r개 선택 후, 2r개 열을 r개 행에 배정
- = C(W-c, 2r) × (2r)! / 2^r
Column-pair: (H-r)개 행에서 2c개 선택 후, 2c개 행을 c개 열에 배정
- = C(H-r, 2c) × (2c)! / 2^c
Isolated 영역의 배치: g[a][b] (동적계획법)

고립 텐트 계산 (g[a][b])

정의: a×b 격자에서 각 행/열마다 최대 1개의 텐트를 배치하는 방법의 수

점화식:

1
g[a][b] = g[a-1][b] + 4×b×g[a-1][b-1]

첫 번째 행이 비는 경우: g[a-1][b]
첫 번째 행에 1개 배치: 4(방향) × b(열선택) × g[a-1][b-1]

베이스 케이스: g[0][b] = 1, g[a][0] = 1

알고리즘 설계

단계별 계산

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
1. 팩토리얼과 역원 전처리 (O(N))
   - fact[i] = i!
   - inv_fact[i] = (i!)^(-1) mod MOD

2. 고립 텐트 DP 계산 (O(H×W))
   - g[a][b] = isolated 영역 배치 수

3. 최종 합계 (O(H×W))
   for r in 0..H:
     for c in 0..W:
       if (W-c >= 2r) and (H-r >= 2c):
         term = C(H,r) × C(W,c) × row_ways × col_ways × g[a][b]
         ans += term

4. 빈 배치 제외 (답 - 1)

복잡도 분석

시간 복잡도: O(H×W) - 전처리 O(N) + DP O(H×W) + 답 계산 O(H×W)
공간 복잡도: O(H×W) - g 배열 저장

구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 3005;

long long fact[2 * MAXN], inv_fact[2 * MAXN];
long long inv2[MAXN];
long long g[MAXN][MAXN];

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int H, W;
    cin >> H >> W;
    
    int LIMIT = 2 * max(H, W) + 5;
    
    // 팩토리얼 전처리
    fact[0] = 1;
    for (int i = 1; i < LIMIT; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv_fact[LIMIT-1] = power(fact[LIMIT-1], MOD-2, MOD);
    for (int i = LIMIT-2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
    
    // 2의 역원 전처리
    long long inv2_single = power(2, MOD-2, MOD);
    inv2[0] = 1;
    for (int i = 1; i <= max(H, W); i++) {
        inv2[i] = inv2[i-1] * inv2_single % MOD;
    }
    
    // 고립 텐트 DP
    for (int b = 0; b <= W; b++) g[0][b] = 1;
    for (int a = 1; a <= H; a++) {
        g[a][0] = 1;
        for (int b = 1; b <= W; b++) {
            g[a][b] = (g[a-1][b] + 4LL * b % MOD * g[a-1][b-1]) % MOD;
        }
    }
    
    long long ans = 0;
    
    // 모든 (r, c) 조합 탐색
    for (int r = 0; r <= H; r++) {
        for (int c = 0; c <= W; c++) {
            // Row-pair 검증: 2r개 열 필요
            if (W - c < 2 * r) continue;
            // Column-pair 검증: 2c개 행 필요
            if (H - r < 2 * c) continue;
            
            int a = H - r - 2 * c; // 고립 텐트 영역 행
            int b = W - c - 2 * r; // 고립 텐트 영역 열
            
            if (a < 0 || b < 0) continue;
            
            long long term = C(H, r) * C(W, c) % MOD;
            
            // Row-pair: C(W-c, 2r) × (2r)! / 2^r
            long long row_ways = C(W - c, 2 * r) * fact[2 * r] % MOD * inv2[r] % MOD;
            
            // Column-pair: C(H-r, 2c) × (2c)! / 2^c
            long long col_ways = C(H - r, 2 * c) * fact[2 * c] % MOD * inv2[c] % MOD;
            
            term = term * row_ways % MOD * col_ways % MOD * g[a][b] % MOD;
            
            ans = (ans + term) % MOD;
        }
    }
    
    // 빈 배치 제외
    ans = (ans - 1 + MOD) % MOD;
    
    cout << ans << "\n";
    
    return 0;
}

코너 케이스 체크리스트

케이스	설명	처리
H=1, W=1	최소 크기	1개 텐트만 가능 (4가지)
H=1, W=2	행 단일	Row-pair 또는 isolated
H=2, W=1	열 단일	Column-pair 또는 isolated
H=100, W=100	최대 크기	모듈로 연산 정확성 검증
R+C가 홀수	패리티	정상 처리