[백준/2673] 교차하지 않는 원의 현들의 최대집합 (Python)

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

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

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : ?? : ?? : ??

 

---

 

문제 설명

 

 

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

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

 

 

 

입력 및 출력

 

입력

 

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

 

출력

 

구한 현의 개수를 출력한다.

 

입력 예시

 

5
97 31
1 45
27 5
11 65
43 72

 

출력 예시

 

3

 

 

---

 

풀이

 

현이라고 생각하면 복잡해지지만, 원주를 펼쳐 하나의 직선으로 생각해 보자. 현은 원주 위의 두 점을 이은 선분으로 변화한다.

 

두 현이 겹치지 않고 동시에 카운팅되는 경우는

• 두 현이 서로를 포함하지 않을 경우
• 한 현이 다른 현을 완벽히 포함할 경우

 

로 볼 수 있다. 따라서 DP를 사용하자. DP[i][j]를 [i, j]범위 내에 최대한 현을 겹치지 않게 현을 세는 경우의 수라고 가정하면, 임의의 k에 대해 DP[i][k] + DP[k][j]와 동일한 결과를 가져온다. (1번 조건). 또한, [i, j]를 잇는 현이 있을 경우, 이렇게 구한 DP 최댓값을 포함할 수 있는 하나의 현이 존재하는 셈이다 (2번 조건) 따라서 수식을 정리하면 DP[i][j] = max(DP[i][k] + DP[k][j]) + L[i][j] 가 된다. (L[i][j]는 [i][j]를 잇는 하나의 현이 존재하는지를 나타내는 값이다)

 

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = 101
N = int(input())
lines = [[0]*MAX for _ in range(MAX)]

for _ in range(N) :
  a, b = map(int, input().split())
  lines[a][b] = lines[b][a] = 1

dp = [[0]*MAX for _ in range(MAX)]

for i in range(1, MAX-1) :
  for j in range(1, MAX-i) :
    for k in range(j, j+i) :
      dp[j][j+i] = max(dp[j][j+i], dp[j][k] + dp[k][j+i] + lines[j][j+i])
print(dp[1][100])

풀이 완료!