[백준] 16439 치킨치킨치킨

문제

• N명의 회원의 만족도가 최대가 되도록 M가지 치킨 중 3개를 주문하려고 한다.
  • 1 <= N <= 30
  • 3 <= M <= 30

 

풀이

• 모든 경우의 수 다 확인하기
  • 모든 치킨 3개 조합 중 회원의 만족도 합이 가장 큰 경우 구하기
  • 효율성을 위해 각 치킨의 회원 만족도 합을 미리 구해 둔다.
    • -> 주의할 점 : 한 사람의 만족도는 시킨 치킨 중 가장 큰 만족도 
• 시간 복잡도 : $_{30}C_{3}$ * N => 계산 가능!

 

from itertools import combinations

N, M = map(int, input().split())    # 회원 수, 치킨 종류 수
# 치킨 선호도 입력 받으면서 각 치킨의 선호도 합 구하기
pref = []
for _ in range(N):
    pref.append(list(map(int, input().split())))

cand = [i for i in range(M)]            # 치킨 후보군
result = 0          # 결과
for c in list(combinations(cand, 3)):   # M개의 치킨 중 3개 선택했을 때,
    now_sum = 0     # 현재 선호도 합
    for i in range(N):
        # 각 사람별 선호도 구하기 (시킨 치킨 중 가장 큰 만족도)
        now_sum += max(pref[i][c[0]], pref[i][c[1]], pref[i][c[2]])
    
    result = max(result, now_sum)       # 만족도가 더 큰 값으로


print(result)

 

References

• 백준 16439번
• 2023/04/22 오늘의 문제