BruteForce15치킨치킨치킨(16439)

문제

N명의 고리 회원들은 치킨을 주문하고자 합니다.
치킨은 총 M가지 종류가 있고 회원마다 특정 치킨의 선호도가 있습니다. 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정됩니다. 진수는 회원들의 만족도의 합이 최대가 되도록 치킨을 주문하고자 합니다.
시키는 치킨의 종류가 많아질수록 치킨을 튀기는 데에 걸리는 시간도 길어지기 때문에 최대 세 가지 종류의 치킨만 시키고자 합니다.
진수를 도와 가능한 만족도의 합의 최댓값을 구해주세요.

입력

첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다.
두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다.
i+1번째 줄에는 i번째 회원의 선호도 ai,1, ai,2, ..., ai,M (1 ≤ ai,j ≤ 9) 가 주어집니다.

출력

첫 번째 줄에 고리 회원들의 만족도의 합의 최댓값을 출력합니다.

풀이

• 먼저 문제 이해가 잘 되지 않았다..
  
  문제 이해는 이러하다.
  치킨 번호가 0 ~ 4 까지 존재하고 조합으로 골라서 각 치킨 선호도의 최대를 구하는 것이다. 따라서 인원이 4명이었을 경우에 최대는
  
  0, 2, 5 번째 치킨이고
  6 + 13(7+6) + 6 이 되어 12인 것이다
• 치킨 3개를 고르는 모든 경우에 대해 이 과정을 진행하고 합의 최댓값을 구하면 된다.
• 조합 3개 경우 구하기, 구한 a,b,c 경우를 for 문으로 최대 3가지 종류 치킨 중에 최대 값을 tmp에 누적한다.(n명 만큼 반복)

코드

import sys
sys.stdin = open("input.txt", "rt")
input = sys.stdin.readline
from itertools import combinations

n, m = map(int, input().split())
like = [list(map(int, input().split())) for _ in range(n)]

maxSum = 0
for a, b, c in combinations(range(m), 3):
    # 0부터 5까지, 3개 조합
    tmpSum = 0
    for i in range(n):
        # 0 부터 4
        # a , b , c 라는 조합을 골라서 max값을 누적한다
        tmpSum += max(like[i][a], like[i][b], like[i][c])
    maxSum = max(maxSum, tmpSum)

print(maxSum)

배운 것

• 조합은 from itertools import combinaions
• 조합을 for 문으로 받을 수 있음!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1

  for a, b, c in combinations(range(m),3)