https://www.acmicpc.net/problem/2262
시간 1초, 메모리 128MB
input :
- n(1≤n≤256)
- n명의 선수들의 랭킹 (1 <= 랭킹 <= n)
output :
- 답을 출력
조건 :
- 랭킹 1, 6, 2, 5, 3, 4위의 선수들이었을 때의 토너먼트 세 개가 위에 있다. A의 경우는 각 시합이 (1 6), (2 5), (3 4), (1 2), (1 3)으로 랭킹 차이의 합이 5+3+1+1+2=12가 된다. 반면에 B는 11이, C는 10이 된다.
다시 한 번 느낍니다...
그리디는 아이디어 찾기가 까다롭네요...
하나의 노드가 경기를 하는 경우는 좌, 우 노드에 대해 경기를 하는 경우 밖에 존재 하지 않는다.
고로 수가 가장 큰 노드를 찾아 좌, 우 노드에 대한 차이를 구해서 그 차가 작은 쪽을 ret 변수에 넣어주고. 가장 큰 노드는 리스트에서 삭제 한다.
이를 노드가 2개 남아있을 때 까지 반복하자.
import sys
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
ret = 0
for i in range(len(data) - 1):
target = max(data)
target_idx = data.index(target)
if target_idx == 0:
ret += target - data[1]
elif target_idx == len(data) - 1:
ret += target - data[-2]
else:
ret = min(ret + target - data[target_idx - 1], ret + target - data[target_idx + 1])
del data[target_idx]
print(ret)
