백준 2673번 교차하지 않는 원의 현들의 최대집합

http://icpc.me/2673

2673번: 교차하지 않는 원의 현들의 최대집합

 

풀이

원의 현이라고 하면 되게 복잡해지고 풀기 싫어집니다.

하지만 두 현의 교차 여부만 중요하다는 점을 잘 생각해 보면 현을 수평선상의 구간으로 생각해도 문제가 없다는 것을 알 수 있습니다. 두 현의 교차하려면 각 현을 나타낸 두 구간이 겹치면서 한 구간이 다른 구간에 포함되지 않아야 합니다. 아래 그림은 예제를 구간으로 나타낸 모습입니다.

 

 

여기까지 왔으면 DP로 문제를 풀 수 있습니다. 

$l_i, r_i$를 $i$번째 구간의 시작과 끝, $F(s, e)$를 $[s, e]$에 속한 구간 중에서 문제의 조건에 맞게 고른 구간의 수의 최댓값이라고 정의하겠습니다. 이렇게 정의하면 문제의 정답은 $F(1, 100)$이 되겠네요.

 

$[s, e]$에 속한 구간이 있다면 $F(s, e)$는 $F(s, l_x - 1) + F(l_x + 1, r_x - 1) + F(r_x + 1, e) + 1$중 최댓값과 같습니다. 위 식은 $x$번째 구간을 사용할 때의 최댓값을 의미합니다. 당연히 $x$번째 구간은 $[s, e]$에 속해야 합니다. $[s, e]$에 속한 구간에 없다면 $F(s, e)$는 자명히 0입니다.

 

모든 구간은 $[1, 100]$에 속하므로 $F(s, e)$를 구할 때마다 모든 구간을 한 번씩 체크해도 $O(N\cdot 100^2)$ 시간복잡도에 문제를 풀 수 있습니다.

코드

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0), cin.tie(nullptr)
using namespace std;
using pii = pair<int, int>;
 
int dp[105][105], n;
vector<pii> chord;
 
int f(int s, int e) {
    if (dp[s][e] != -1) return dp[s][e];
    dp[s][e] = 0;
    for (auto& [l, r] : chord) {
        if (l < s or e < r) continue;
        dp[s][e] = max(dp[s][e], f(s, l - 1) + f(l + 1, r - 1) + f(r + 1, e) + 1);
    }
    return dp[s][e];
}
 
int main() {
    fast;
    memset(dp, -1, sizeof dp);
    cin >> n;
    chord.resize(n);
    for (auto& [l, r] : chord) {
        cin >> l >> r;
        if (l > r) swap(l, r);
    }
    cout << f(1, 100);
}

 

사족

어려워요