[도전 23일차] 교차하지 않는 원의 현들의 최대 집합 풀이

※복습 : 

 

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

문제 링크

 

사용 알고리즘 : DP

 

풀이:

 

일단 먼저 두 현이 겹치는지 파악하는 방법을 생각해보자.

두 현을 각각 (a,b) , (c,d)라고 하면 교차하는지 파악하는 방법은 다음과 같다.

bool cross(int a,int b,int c,int d){
	if(a>b)a^=b^=a^=b;
	return (a<c&&c<b)^(a<d&&d<b);
}

심심해서 넣어봤다.

 

풀이는 DP다. DP 식 세우다가 뇌절 와서 풀이를 봤는데 그렇게 와닿지는 않았다. 이해는 됐는데 사고의 흐름을 못 따라갔다고 해야될까.

 

DT[s][e] 를 원 위의 s~e 번 점까지 봤을 때 고를 수 있는 최대 현의 개수라 정의하자.

  s<=k<=e 에 대해 ,( k, e) 인 현이 존재한다면 A[k][e] = 1 , 존재하지 않으면 0이라 하자.

 

// DT : Dynamic Table

$$DT[s][e] = max_{s <= k <= e} (DT[s][k-1] + DT[k+1][e-1] + A[k][e])$$

의 관계식을 이용해 DP를 채우면 된다.

DP[s] [ e] 를 채우기 위해 DP[k+1][e-1] 이 필요하므로 

e는 작은 것, s는 큰 것부터 채우면 된다는 것을 알 수 있다.

 

코드는 엄청 간단하다. 그런데, 아이디어 자체도 간단하고 구현도 쉽기 때문에 사고 방식 자체를 배우는게 중요하다. 

 

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define vsort(v) sort(v.begin(),v.end())
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
const int INF = 1e9;
using namespace std;
int n,DT[110][110];
bool A[101][101];
int main(){
    fastIO;
    cin>>n;
    for(int i=0,a,b;i<n;i++){
        cin>>a>>b;
        A[a][b]=A[b][a]=1;
    }
    for(int e=1;e<=100;e++)
        for(int s=e-1;s>=1;s--){
            int ans=0;
            for(int k=s;k<=e;k++)
                ans=max(ans,DT[s][k-1]+DT[k+1][e-1]+A[k][e]);
            DT[s][e]=ans;
        }
    cout<<DT[1][100];
}

 

버스 노선 문제와 닮았다. 풀이 방법은 전혀 다른 것이 함정.

[도전 2일차] 세 용액, 버스 노선

궁금한 점이 있으시다면 질문 남겨주세요 :)