[Algorithm] cpp-python 백준 12735번: Boat

문제

링크: https://www.acmicpc.net/problem/12735
요약: 각 학교 i는 [ai, bi] 대수의 보트를 낼 수 있고(안 낼 수도 있음), 만약 낸다면 i보다 작은 번호 학교들이 낸 모든 수보다 더 많은 보트를 내야 합니다. 한 학교 이상이 내는 모든 배치 수를 구해 1,000,000,007로 나눈 값을 출력합니다.

입력/출력

1
2
3
4
5
6
7
8
9
입력
N
a1 b1
a2 b2
...
aN bN

출력
정답 (모듈러 1,000,000,007)

접근 개요

핵심 관찰: 선택된 학교 인덱스가 증가할수록 보트 수도 엄격히 증가해야 하므로, 최종적으로는 (인덱스, 보트 수) 쌍이 인덱스 오름차순, 보트 수 엄격 증가를 만족하는 수열의 개수 카운팅 문제입니다.
ai, bi가 최대 1e9이므로 값의 범위가 커 직접 순회 불가. 구간의 경계만 의미 있으므로 모든 ai와 (bi+1)을 모아 좌표압축 후, 인접한 압축 좌표 [st, ed) 구간을 길이 L=ed-st로 순회합니다.
각 구간 [st, ed) 동안 그 구간을 완전히 덮는 후보 학교들만 고려해, 이번 구간에서 k개를 고르고 마지막 후보 인덱스가 j일 때의 조합 수를 dp2[k][j]로 누적(prefix) 계산합니다.
조합 항은 (L−k+1)/k가 곱해지는 형태로 나타나 모듈러 역원을 사용합니다. 이전 구간까지의 상태 dp를 부분합(pref)로 관리하여 k=1 전이도 O(1)로 처리합니다.

flowchart LR
    A[좌표압축된 점들 v[0..M])]
    A --> B([각 인접 구간 i: [v[i-1], v[i]) 길이 L])
    B --> C{구간을 완전히 덮는 학교 후보 cnd[] 추출}
    C --> D[dp2[k][j] 누적 전이 (모듈러 역원 사용)]
    D --> E[dp[cnd[j]] 갱신]
    E --> F[다음 구간으로]

알고리즘 설계

상태 정의
- dp[j]: 지금까지 처리한 구간 전체에서 마지막으로 선택된 학교가 j일 때의 경우의 수 (dp[0]=1은 시작 상태)
- dp2[k][j]: 현재 구간에서 k개 선택했고, 후보 배열 cnd의 j번째 학교가 마지막일 때의 누적(prefix) 합
전이 요약(구간 길이 L, 후보 크기 K)
- 후보는 cnd[j]가 [st, ed) 전체를 덮는 학교만 포함
- k=1: dp2[1][j] = dp2[1][j-1] + (sum(dp[0..cnd[j]-1]) * L)
- k≥2: dp2[k][j] = dp2[k][j-1] + dp2[k-1][j-1] * (L - k + 1) / k (모듈러 역원으로 나눗셈 처리)
- 이후 dp에 이번 구간 기여를 차분(= dp2[k][j] - dp2[k][j-1])로 반영: dp[cnd[j]] += 차분값

복잡도

좌표 수는 최대 2N, 각 구간마다 후보 크기(K)와 L에 대해 위 전이를 수행합니다.
최악 시간 복잡도: O(N^3) (APIO 공식 풀이와 동일 추정). 공간: O(N^2) 수준(dp2).

구현 (C++)

 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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
const int MOD = 1'000'000'007;

int64 modPow(int64 a, int64 e) {
	int64 r = 1;
	while (e) {
		if (e & 1) r = (r * a) % MOD;
		a = (a * a) % MOD;
		e >>= 1;
	}
	return r;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	if (!(cin >> n)) return 0;
	vector<long long> a(n + 1), b(n + 1);
	vector<long long> coords;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
		b[i]++; // [a, b+1) 로 변환
		coords.push_back(a[i]);
		coords.push_back(b[i]);
	}
	sort(coords.begin(), coords.end());
	coords.erase(unique(coords.begin(), coords.end()), coords.end());
	
	static long long inv[1005];
	for (int i = 1; i <= 1000; ++i) inv[i] = modPow(i, MOD - 2);

	static long long dp[505], pref[505];
	static long long dp2[505][505];
	dp[0] = 1; // 시작 상태

	for (size_t t = 1; t < coords.size(); ++t) {
		long long st = coords[t - 1], ed = coords[t];
		long long L = ed - st;
		if (L <= 0) continue;

		vector<int> cnd;
		pref[0] = 1; // dp[0] 포함
		for (int j = 1; j <= n; ++j) {
			pref[j] = (pref[j - 1] + dp[j]) % MOD;
			if (a[j] <= st && ed <= b[j]) cnd.push_back(j);
		}
		int K = (int)cnd.size();
		if (K == 0) continue;

		int upto = (int)min<long long>(K, L);
		for (int k = 1; k <= upto; ++k) {
			for (int j = k - 1; j < K; ++j) {
				if (k == 1) {
					int idx = cnd[j] - 1;
					long long val = (pref[idx] * (L % MOD)) % MOD;
					if (j) val = (val + dp2[k][j - 1]) % MOD;
					dp2[k][j] = val;
				} else {
					long long add = (dp2[k - 1][j - 1] * inv[k]) % MOD;
					add = (add * ((L - k + 1) % MOD)) % MOD;
					long long val = add;
					if (j) val = (val + dp2[k][j - 1]) % MOD;
					dp2[k][j] = val;
				}
			}
		}
		for (int k = 1; k <= upto; ++k) {
			for (int j = k - 1; j < K; ++j) {
				long long cur = dp2[k][j];
				if (j) cur = (cur - dp2[k][j - 1] + MOD) % MOD;
				dp[cnd[j]] += cur;
				if (dp[cnd[j]] >= MOD) dp[cnd[j]] -= MOD;
			}
		}
	}

	long long ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans += dp[i];
		if (ans >= MOD) ans -= MOD;
	}
	cout << ans << '\n';
	return 0;
}

구현 (Python)

 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
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys
input = sys.stdin.readline

MOD = 1_000_000_007

n_line = input().split()
if not n_line:
    sys.exit(0)
n = int(n_line[0])

a = [0] * (n + 1)
b = [0] * (n + 1)
coords = []
for i in range(1, n + 1):
    ai, bi = map(int, input().split())
    a[i] = ai
    b[i] = bi + 1
    coords.append(ai)
    coords.append(b[i])

coords = sorted(set(coords))

inv = [0] * 1005
for i in range(1, 1001):
    inv[i] = pow(i, MOD - 2, MOD)

dp = [0] * (n + 1)
pref = [0] * (n + 1)
dp2 = [[0] * (n + 1) for _ in range(n + 1)]
dp[0] = 1

for t in range(1, len(coords)):
    st, ed = coords[t - 1], coords[t]
    L = ed - st
    if L <= 0:
        continue

    cnd = []
    pref[0] = 1
    for j in range(1, n + 1):
        pref[j] = (pref[j - 1] + dp[j]) % MOD
        if a[j] <= st and ed <= b[j]:
            cnd.append(j)

    K = len(cnd)
    if K == 0:
        continue

    upto = min(K, L)
    for k in range(1, upto + 1):
        base = 0
        if k == 1:
            mul = L % MOD
            for j in range(k - 1, K):
                idx = cnd[j] - 1
                val = (pref[idx] * mul) % MOD
                base = (base + val) % MOD
                dp2[k][j] = base
        else:
            mul = (inv[k] * ((L - k + 1) % MOD)) % MOD
            prev_row = dp2[k - 1]
            for j in range(k - 1, K):
                val = (prev_row[j - 1] * mul) % MOD
                base = (base + val) % MOD
                dp2[k][j] = base

    for k in range(1, upto + 1):
        prev = 0
        for j in range(k - 1, K):
            cur = dp2[k][j]
            add = (cur - prev) % MOD
            dp[cnd[j]] = (dp[cnd[j]] + add) % MOD
            prev = cur

ans = sum(dp[1:]) % MOD
print(ans)