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

• 문제 링크 : boj.kr/2673
• 난이도 : P4
• 태그 : DP

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    int edge[101][101] = {};
    int dp[101][101] = {};
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if(a>b) swap(a,b);
        edge[a][b] = 1;
    }
    
    for(int d = 0; d < 100; d++) {
        for(int i = 1; i <= 100-d; i++) {
            for(int k = 0; k < d; k++) {
                dp[i][i+d] = max(dp[i][i+d], dp[i][i+k] + dp[i+k][i+d] + edge[i][i+d]);
            }
        }
    }
    cout << dp[1][100];

    return 0;
}

---

풀이

원은 불편하므로 직선으로 펼쳐보자. 주어진 현의 두 점을 a, b (a < b)로 나타내면 직선 위에 선분으로 나타낼 수 있다.

현이 교차한다는 것은 직선 위에 나타낸 두 선분이 일부만 겹치는 것을 의미한다. 더 자세히 말해 ai < bi < aj < bj 라면 두 선분이 교차한다.

이 조건을 놓고 보면 괄호 문자열이 떠오른다. 괄호 문자열이 올바를 조건을 이용해보자.

올바른 괄호 문자열 두 개를 나란히 놓은 것은 올바른 괄호 문자열이다.

올바른 괄호 문자열을 올바른 괄호 쌍으로 감싼 것도 올바른 괄호 문자열이다.

여기서 힌트를 얻어 DP[i][j] = max(DP[i][j], DP[i][k]+DP[k][j] + Edge[i][j])라는 점화식을 얻을 수 있다.

k-i < j-i, j-k < j-i이므로 차이가 작은 구간부터 DP배열을 채우면 답을 구할 수 있다.