[백준 23762번] 파이썬 - 배드민턴 복식 팀 만들기

http://www.acmicpc.net/problem/23762

23762번: 배드민턴 복식 팀 만들기

 

# 조건

• 고려대학교 배드민턴 동아리원들이 배드민턴을 치려고 한다. 모두가 동시에 재밌게 배드민턴을 치기 위해, 동아리원들의 각각의 실력을 고려하여 다음과 같이 복식 팀을 만들려고 한다.
• 배드민턴 복식은 2명이 짝을 지어 대결하기 때문에, 양쪽에서 총 4명이 한 팀을 이루어 게임을 진행한다. 
• 또한 모든 사람의 배드민턴 실력을 자연수로 나타낼 수 있다. 이 때 각 팀의 (실력 최댓값) - (실력 최솟값) 을 그 팀의 실력차라 하자.
• 비슷한 실력대의 사람들끼리 배드민턴을 쳐야 재미있게 칠 수 있으므로, 실력차가 작을수록 게임이 재미있다. 또한 실력차와 별개로 배드민턴을 치지 않는 것이 가장 재미가 없기 때문에, 팀을 가능한 한 많이 만들어야 한다.
• 지금은 사람이 많아 여러 팀을 만들어야 하므로, 모든 팀의 실력차의 총합이 최소가 되도록 해야 한다. 그런데 배드민턴에 참여한 인원수가 4의 배수가 아닐 수 있으므로, 누군가는 배드민턴을 치지 못할 수 있다.
• 실력차의 합이 최소가 되도록 팀을 구성할 때, 실력차의 합의 최솟값과 배드민턴을 치지 못하는 사람들이 누군지 구하는 프로그램을 작성하시오.

 

# 접근 방법

• 우선 실력순으로 정렬을 해주며 그 사람의 번호를 알기 위해 enumerate를 통해 index도 저장해준다.
• i-3 ~ i번째 4명을 한 팀으로 모았을 때의 실력차를 기록해준다.
• 이 때, 복식 팀을 짜는 경우의 수를 생각해보자
• 핵심은 -> 정렬이 되어있으므로 4명이 연속으로 팀을 하는 것이 최솟값이다.
• 또한, 팀을 이루지 못하는 깍두기 리스트를 만들어 주어 dp 테이블을 갱신하며 깍두기 리스트를 함께 갱신해준다.
  • 4명씩 딱 떨어지는 경우 -> 4명씩 끊으며 최솟값 더해준다.
  • 1,2,3명이 떨어지는 경우 -> 한 칸씩 움직이며 지금 내가 포함된 팀 = i-3~ i 가 i-4~i-1 즉, dp[i-1] 의 값보다 작다면 갱신을 해준다.
  • 깍두기 리스트에 ls[i-4]의 값을 추가해주는 것이 중요!

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
  
N = int(input())  
# 실력 순 오름차순 + 인덱스도 저장  
person = sorted(enumerate([*map(int, input().split())]), key =lambda x: x[1])  
  
# 인덱스와 실력 따로 저장  
idx, ability = [], []  
for a, b in person:  
    idx.append(a)  
    ability.append(b)  
  
# i-3~i 번째 실력차이 저장 리스트  
# 최대한 크게 저장해주어야 나중에 최솟값으로 갱신 가능  
diff = [1e9] * N  
for i in range(3,N):  
    diff[i] = ability[i] - ability[i-3]  
  
# 깍두기 리스트 ls  
# 처음 4명까지 빠지는 사람의 인덱스 번호  
# 4명이 되기 전까지 0번째 -> 0번, 1번째 -> 0번과 1번, 2번째 -> 0, 1, 2번의 사람이 참가를 못한다.  
ls = [[0], [0,1], [0,1,2], []]  
  
# 실력차 합의 최소값 dp  
# dp[3] => 처음 4명이 되는 값이므로 diff[3]과 동일  
dp = [0] * N  
dp[3] = diff[3]  
  
# 테이블 갱신  
for i in range(4, N):  
    # 나머지가 3이면 모두 4명씩 묶이는 경우의 수이므로 dp[i-4] + diff[i]의 값이 된다.  
    if i % 4 == 3:  
        dp[i] = dp[i-4] + diff[i]  
        ls.append([])  
    else:  
        # 연속된 4명의 합이 최소이므로 지금 내가 이루는 4명 -> 4번째 전 사람이 빠졌을 때의 값과 비교  
        # 즉 0~3번의 사람과 1~4번의 사람의 값을 비교하여 작은 것으로 갱신        # 작은 쪽이 앞이라면, 현재 사람은 깍두기로 넣어준다.        # 아니라면, i-4번째 사람이 깍두기가 되어야 한다.
		if dp[i-1] < dp[i-4] + diff[i]:  
            dp[i] = dp[i-1]  
            ls.append(ls[i-1] + [i])  
        else:  
            dp[i] = dp[i-4] + diff[i]  
            ls.append(ls[i-4])  
  
print(dp[-1])  
for a in ls[-1]:  
    print(idx[a])