[백준] 16439 번 - 치킨치킨치킨- python[ brute foce, 조합 ]

[Silver IV] 치킨치킨치킨 - 16439

문제 링크

성능 요약

메모리: 31120 KB, 시간: 64 ms

분류

브루트포스 알고리즘

제출 일자

2024년 10월 7일 16:50:09

문제 설명

N명의 고리 회원들은 치킨을 주문하고자 합니다.

치킨은 총 M가지 종류가 있고 회원마다 특정 치킨의 선호도가 있습니다. 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정됩니다. 진수는 회원들의 만족도의 합이 최대가 되도록 치킨을 주문하고자 합니다.

시키는 치킨의 종류가 많아질수록 치킨을 튀기는 데에 걸리는 시간도 길어지기 때문에 최대 세 가지 종류의 치킨만 시키고자 합니다.

진수를 도와 가능한 만족도의 합의 최댓값을 구해주세요.

입력

첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다.

두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다.

i+1번째 줄에는 i번째 회원의 선호도 a_i,1, a_i,2, ..., a_i,M (1 ≤ a_i,j ≤ 9) 가 주어집니다.

출력

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

나의 풀이

조합을 사용하여 치킨을 선택하는 모든 경우의 수에 대해 가장 큰 값을 구하는 방식이다.

import sys

def input():
    return sys.stdin.readline().rstrip()

n,m = map(int,input().split())
chickens = {}
answer = -1

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

sem = [0,0,0]
def comb(index,semIndex):
    global answer

    if semIndex == 3:
        temp = 0
        for j in range(n):
            temp += max([chickens[j][key] for key in sem])
        if temp > answer: 
            answer = temp
        return

    if index == m:
        return

    sem[semIndex] = index
    comb(index+1, semIndex+1)
    comb(index+1, semIndex)

comb(0,0)
print(answer)