백준 16439 - 치킨치킨치킨

https://www.acmicpc.net/problem/16439

풀이

1. N명의 사람들이 M가지의 치킨을 평가한 점수표가 주어진다.
2. 각각의 사람은 M가지 치킨에 대한 선호도를 숫자로 나타낸다.
3. 3가지 치킨을 선택했을 때, 사람들이 가장 좋아하는 치킨 중 최대값을 모두 합한 값이 최대가 되도록 해야 한다.

브루트포스 알고리즘을 사용해서 해결 할 수 있다.

가능한 모든 3가지 치킨 조합을 확인하고, 각 조합에 대해 점수를 계산하여 최대 값을 찾는다.

1. 모든 M개의 치킨 중 3개를 선택하는 조합을 combination으로 가져온다.
2. N명의 사람들에 대해, 선택된 3개의 치킨 중 가장 높은 점수를 max_like에 저장하고, 이를 sum에 추가한다.
3. 모든 조합을 돌면서 최대 sum값을 max_sum에 저장한다.

코드

# 백준 16439 - 치킨치킨치킨
# 분류 : 브루트포스

from itertools import combinations

N, M = map(int, input().split())
A = [[] for _ in range(N)]

for i in range(N):
    A[i] = list(map(int, input().split()))

max_sum = 0
for combination in combinations(range(M), 3) :
    sum = 0
    for i in range(N) :
            max_like = 0
            for j in combination :
                max_like = max(max_like, A[i][j])
            sum += max_like
    
    max_sum = max(max_sum, sum)

print(max_sum)