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

https://www.acmicpc.net/problem/2673

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

 

- 문제 요약

 

평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로 붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들 중에서 서로 교차하지 않는 것들을 최대한 많이 찾아서 그 개수를 출력하는 프로그램을 작성하라.

단, 1 ≤ N ≤ 50이고, 주어진 각 점은 많아야 한 현의 끝점이 될 수 있다.

첫 번째 줄은 주어지는 현의 개수 N이고, 다음의 N줄은 각 현의 양 끝점의 번호가 주어진다.

 

 

- 알고리즘 정리

 

dp[i][j] : i, i+1 ~ j 인덱스에 있는 점들을 끝점으로 하고, 교차 선분이 없는 선분들의 최대 집합 크기
num[i][j] : i, j를 잇는 선분이 있는가? (있으면 1, 아니면 0)
dp[j][i] = max( dp[j][i] , dp[j][k] + dp[k][i] + num[i][j] )

 

 

- 코드 정리

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 101
int n,dp[MAX][MAX],num[MAX][MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		num[a][b]=num[b][a]=1;
	}
	for(int i=1;i<=100;i++){
		for(int j=i;j>=1;j--){
			for(int k=j;k<i;k++){
				dp[j][i]=max(dp[j][i],dp[j][k]+dp[k][i]+num[i][j]);
			}
		}
	}
	cout<<dp[1][100];
}

코드 제출 결과