[풀이실패]_백준에서 sostkr94님의 풀이 참조
문제
월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러도 랭킹이 높은 사람이 반드시 이기게 된다. 따라서 월드시에서는 게임을 흥미진진하게 만들기 위해서, 부전승을 여러 번 만들더라도 각 시합에 임하는 선수들의 랭킹 차이를 비슷하게 만들려고 한다.
토너먼트를 만들 때에는 이미 추첨이 된 순서대로 선수들을 배치하고, 왼쪽에서 오른쪽의 순서가 어긋나지 않도록 시합을 정한다. 물론 부전승을 임의로 만들 수 있지만, 토너먼트가 꼬여서는 안 된다. 또한, 각 시합에 임하는 두 선수의 랭킹의 차이의 합이 최소가 되도록 하려 한다.
예를 들어 추첨 결과가 차례로 랭킹 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이 된다.
토너먼트 추첨 결과가 주어졌을 때, 각 시합에 임하는 두 선수의 랭킹 차이의 총 합의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 n(1≤n≤256)이 주어진다. 다음 줄에는 추첨 결과를 나타내는 n명의 선수들의 랭킹이 주어진다. 각 선수의 랭킹은 1부터 n까지의 자연수로 나타나며, 랭킹이 같은 경우는 없다고 가정하자.
입력예시
6
1 6 2 5 3 4출력
출력예시
9풀이
처음에는 모든 선수들을 3명씩 끊어서 양쪽의 차이를 비교하여 부전승을 결정하고 랭킹 차를 더해나가는 방식으로 했었는데 만약 (1,2,3)과 같이 양쪽에서 선수들의 랭킹 차이가 같은 경우에 예외가 복잡해져서 풀이가 계속 꼬이면서 결국 해결을 하지 못했다. 문제를 전체적으로 보고 접근했었어야 했는데 그렇게하지 못했던것 같다.
다른 답을 찾아본 결과, 랭킹이 가장 낮은 선수를 찾아서 그 선수의 양쪽 중에 랭킹 차가 더 작은 사람과 토너먼트를 진행한다. 가장 랭킹이 낮은 선수는 어차피 우승하지 못하기 때문에 그 선수를 목록에서 제외(pop)시키고 앞선 방식을 반복하면 된다.
반대로 랭킹이 가장 높은 선수들부터 토너먼트를 진행한다면 어떻게될까? 양쪽에서 랭킹 차가 적은 선수들을 선택한다고해도 다음 경기에서 붙게되는 선수는 이전 선수보다 더 랭킹이 낮은 선수일 것이고 그럼 랭킹 차가 더 커지게 된다. 그렇기 때문에 위와 같이 랭킹이 가장 낮은 선수부터 진행해야 하는 것이었다.
num = int(input())
players = list(map(int, input().split()))
count = 0
while(True):
MAX = max(players)
lowest = players.index(MAX)
num = len(players)
# 처음에는 이 if문을 while문의 맨 끝에 위치시켰는데
# vscode에서는 답이 잘 나왔지만 백준 채점에서는 런타임 에러가 발생했다.
# 그래서 위치를 바꿔보니 채점에 성공했다. 이유가 뭘까?
if num==1:
print(count)
break
if lowest==0:
gap = players[lowest]-players[lowest+1]
elif lowest==(num-1):
gap = players[lowest]-players[lowest-1]
else:
if players[lowest-1] > players[lowest+1]:
gap = players[lowest]-players[lowest-1]
else:
gap = players[lowest]-players[lowest+1]
count += gap
players.pop(lowest)