16439번: 치킨치킨치킨
첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다. 두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다. i+1번째 줄에는 i번째 회원의 선
www.acmicpc.net
문제
N명의 고리 회원들은 치킨을 주문하고자 합니다.
치킨은 총 M가지 종류가 있고 회원마다 특정 치킨의 선호도가 있습니다. 한 사람의 만족도는 시킨 치킨 중에서 선호도가 가장 큰 값으로 결정됩니다. 진수는 회원들의 만족도의 합이 최대가 되도록 치킨을 주문하고자 합니다.
시키는 치킨의 종류가 많아질수록 치킨을 튀기는 데에 걸리는 시간도 길어지기 때문에 최대 세 가지 종류의 치킨만 시키고자 합니다.
진수를 도와 가능한 만족도의 합의 최댓값을 구해주세요.
입력
첫 번째 줄에 고리 회원의 수 N (1 ≤ N ≤ 30) 과 치킨 종류의 수 M (3 ≤ M ≤ 30) 이 주어집니다.
두 번째 줄부터 N개의 줄에 각 회원의 치킨 선호도가 주어집니다.
i+1번째 줄에는 i번째 회원의 선호도 ai,1, ai,2, ..., ai,M (1 ≤ ai,j ≤ 9) 가 주어집니다.
출력
첫 번째 줄에 고리 회원들의 만족도의 합의 최댓값을 출력합니다.
코드
from itertools import combinations
n, m = map(int, input().split())
preference = []
for i in range(n):
preference.append(list(map(int, input().split())))
def get_satisfaction(memeber, orders):
max_pref = 0
for i in [preference[memeber][j] for j in orders]:
max_pref = max(max_pref, i)
return max_pref
ans = 0
for orders in list(combinations(range(m), 3)):
total = 0
for i in range(n):
total += get_satisfaction(i, orders)
ans = max(ans, total)
print(ans)
치킨의 종류가 최대 30가지여서 최대 $_{30}C_3 = 4060$으로 경우의 수가 적다. 회원의 수도 최대 30명이므로 모든 경우의 수를 탐색해봐도 된다.
'문제풀이 > 완전탐색' 카테고리의 다른 글
[Python/파이썬] 백준 15970번 화살표 그리기 (1) | 2024.02.03 |
---|---|
[Python/파이썬] 백준 1025번 제곱수 찾기 (0) | 2024.01.11 |
[Python/파이썬] 백준 5568번 카드 놓기 (0) | 2023.04.27 |
[Python/파이썬] 백준 1969번 DNA (0) | 2023.04.27 |
[Python/파이썬] 백준 18511번 큰 수 구성하기 (0) | 2023.04.26 |