[이상한 토너먼트/G2/Python3]

15321번 이상한 토너먼트 G2

 

문제
천하제일코딩대회가 열리게 되었다. 천하제일코딩대회는 1대 1 대결 토너먼트 방식으로 진행이 된다. 대회 운영을 맡은 전설의 코더 천민호는 개인의 코딩실력을 정확히 측정하는 스카우터를 만들어 각 참가자의 코딩력(능력치)을 알고 있다. 코딩력이 다른 두 사람이 대결을 하게되면 무조건 코딩력이 높은 사람이 승리하게 된다. (사실상 우승자는 정해져있는 것이나 다름없다.) 토너먼트 대진표를 작성하기 귀찮았던 민호는 우선 참가신청한 사람들의 순서대로 일렬로 나열한 후, 선을 그어 대진표를 완성하려 한다. 민호는 대회의 재미를 위해서 관중들이 지루하지 않도록 대진표를 완성하고 싶다. 일반적으로 관중들의 지루함 정도는 두 대결자의 코딩력의 차에 비례한다. 관중들의 지루함 = 두 대결자의 코딩력 차라고 하였을 때, 모든 토너먼트가 끝난 후 지루함의 합이 최소가 되도록 대진표를 작성하려 한다. 이때, 지루함의 합을 구하여라.대진표의 선을 어떻게 작성하냐에 따라 각 참가자의 경기수는 다를 수 있다. 대진표의 선이 교차되게 작성하면 안 된다. (이웃한 두 그룹 간 대결할 수 있다.)

입력
첫째 줄에 총참가자의 수 N(2 ≤ N ≤ 500)이 주어진다. 그 후 N줄에 걸쳐 참가신청한 순서에 맞추어 코딩력 Xi (1 ≤ Xi ≤ 100,000)이 주어진다. 코딩력이 같은 참가자는 없다.

출력
대진표를 최적의 경우로 작성하였을 때, 총 지루함의 값을 출력한다.

 

 

다이나믹 프로그래밍, 그리디 알고리즘

 

 

O(n^2) 시간 복잡도로 풀이했다.

시간 제한은 2초, 입력 조건도 크지 않아 시간제한은 여유롭게 통과했다.

 

현재 가장 작은 원소를 항상 대진 시키는 탐욕적인 방식으로 풀이를 하였다.

 

각 원소들의 차는 먼저 구해두고, dp에 저장을 해둔다.

우선순위 큐로 가장 작은 원소와 그의 인덱스를 받아왔다.

 

가장 작은 원소의 양옆 중 토너먼트가 가능한 대상만 검색해야 하므로, 이미 진 여부를 확인하는 bool 변수를 추가했다.

 

 

import sys
import heapq

n = int(sys.stdin.readline())
fusion = [False] * n
subs = [0] * n
dp = [[0] * n for _ in range(n)]
for i in range(n): subs[i] = int(sys.stdin.readline())

hq = []
for i in range(n-1):
    for j in range(i+1, n):
        dp[i][j] = abs(subs[i] - subs[j])
        dp[j][i] = abs(subs[i] - subs[j])

for i in range(n): heapq.heappush(hq, (subs[i], i))

def find(v):
    check = 100001
    for i in range(v-1, -1, -1):
        if fusion[i]: continue
        check = dp[v][i]
        break
    for i in range(v+1, n, 1):
        if fusion[i]: continue
        check = min(dp[v][i], check)
        break
    return check

result = 0
while len(hq) > 1:
    v, i = heapq.heappop(hq)
    fusion[i] = True
    result += find(i)
print(result)

 

---

 

dp로 먼저 저장하는 아이디어와 그리디의 최적해를 구하는 것이 중요했던 문제였다.