28446 : 좋은 팀이란? - Python

접근

---

팀원 구성 점수 아래 요소들의 합계이다.

• (X, Y), (Y, Z), (X, Z) 의 천간 관계 점수, 지지 관계 점수
• X, Y, Z의 실력 값의 합계

그렇다면 결국 메모는 필요한데 배열과 dict를 고민하던 중 조합을 사용해야 하는데 N이 10^6까지 가능하므로 비트마스킹을 쓰기에는 너무 크다고 판단하여 dict를 사용하기로 했다. dict를 사용해서 2가지 조합을 미리 만들고 여기서 한 명을 더 추가하는 식으로 하려고 했었는데 이를 구현하지 못했다.

 

결국 시간이 꽤 흘렀고 알고리즘을 확인해보니 비둘기집 원리 문제였다.

 

풀이

---

비슷한 유형을 풀어보고 싶다면 이 문제를 풀어보자.

 

비둘기집 원리란 비둘기 집이 N개있고, N 보다 큰 M 마리의 비둘기가 있다고 가정하자. 이 때 최소 한 마리 이상의 비둘기는 다른 비둘기와 같은 집을 공유한다는 것을 의미한다. 수많은 비둘기보다 한정된 비둘기 집에 집중하면 경우의 수를 많이 줄일 수 있다.

 

이 문제에서는 최대 1,000,000명의 사람과 총 60 개의 사주가 있기 때문에 모든 사람은 60개의 사주로 구분될 수 있다.

여기서 각 사주마다 개인점수가 가장 높은 사람으로 갱신하면 되는 문제다. 왜? 두 사주의 관계에서 나오는 점수는 항상 같고 개인 점수에서만 차이가 난다.

 

좀 더 생각해보니 같은 사주인 3명이 한 팀이 되는 경우도 있을 수 있으므로 사주별로 3명의 점수를 관리해야 했다. 개인 점수는 힙을 사용해 내림차순으로 저장했다.

three_by_categories = []
for saju, scores in people.items():
    cnt = 0
    while scores and cnt < 3:
        three_by_categories.append((saju, heappop(scores)[1]))
        cnt += 1

위에서 defaultdict로 각 사주별로 힙을 만들고 내림차순으로 저장했다. 이제 각 사주별로 최대 3개까지 사주와 개인 점수를 튜플로 묶고 리스트에 넣었다.

 

for x, y, z in combinations(three_by_categories, 3):
    ans = max(calc(x, y, z), ans)

그 뒤 itertools를 이용해 위에서 만든 리스트에서 3개의 사주를 뽑아 조합을 만들었다. 그리고 점수를 최댓값을 갱신시켜주면 된다.

분명 더 좋은 풀이 방법이 있을텐데 생각이 굳어서 이 방식이 최선이였다.

하지만 풀었죠?

 

전체 코드

---

import sys
from collections import defaultdict
from heapq import heappop, heappush
from itertools import combinations

# print = sys.stdout.write
input = sys.stdin.readline
# 반드시 아래 두 라인 주석 처리 후 제출
# f = open("input.txt", "rt")
# input = f.readline
# 반드시 위 두 라인 주석 처리 후 제출
MAX_IDX1, MAX_IDX2 = 10, 12

people = defaultdict(lambda: [])

N = int(input().rstrip())
cheongan = [list(map(int, input().split())) for _ in range(MAX_IDX1)]
jiji = [list(map(int, input().split())) for _ in range(MAX_IDX2)]

def calc(x, y, z):
    x_idx, y_idx, z_idx = segregate(x), segregate(y), segregate(z)
    xy = cheongan[x_idx[0]][y_idx[0]] + jiji[x_idx[1]][y_idx[1]]
    yz = cheongan[y_idx[0]][z_idx[0]] + jiji[y_idx[1]][z_idx[1]]
    zx = cheongan[z_idx[0]][x_idx[0]] + jiji[z_idx[1]][x_idx[1]]
    return xy + yz + zx + x[1] + y[1] + z[1]

def segregate(saju):
    # 사주의 각 글자를 인덱스로 바꿔줌
    return int(saju[0][0]), ord(saju[0][1]) - 65

three_by_categories = []

def main():
    for _ in range(N):
        performance, saju = input().split()
        performance = int(performance)
        heappush(people[saju], (-performance, performance))

    ans = 0
    for saju, scores in people.items():
        cnt = 0
        while scores and cnt < 3:
            three_by_categories.append((saju, heappop(scores)[1]))
            cnt += 1

    for x, y, z in combinations(three_by_categories, 3):
        ans = max(calc(x, y, z), ans)

    print(ans)

if __name__ == "__main__":
    main()