[Python] 백준 16439 치킨치킨치킨 (Brute Force)

선주·2022년 3월 12일
0

Python PS

목록 보기
59/65
post-thumbnail

📌 문제

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

3 5
1 2 3 4 5
5 4 3 2 1
1 2 3 2 1

예제 출력 1

13

예제 입력 2

4 6
1 2 3 4 5 6
6 5 4 3 2 1
3 2 7 9 2 5
4 5 6 3 2 1

예제 출력 2

25

📌 풀이

💬 Code

import sys
from itertools import combinations
input = sys.stdin.readline

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):
    tmpSum = 0
    for i in range(n):
        tmpSum += max(like[i][a], like[i][b], like[i][c])
    maxSum = max(maxSum, tmpSum)

print(maxSum)

💡 Solution

  • like: 회원들의 치킨 선호도가 담긴 리스트
  • combinations(range(m), 3): 치킨이 m종류이므로 0, 1, 2, 3, …, m-1번 치킨 중 3개를 고른 조합
  • tmpSum: 고른 a, b, c번 치킨에 대한 각 회원의 최대 선호도를 더한 값
  • maxSum: tmpSum 중 가장 큰 값

처음엔 문제가 이해가 안 가서 몇 번을 다시 읽었다 😵 예제 1이 입력으로 주어지는 경우를 보면

0 1 2 3 4 (치킨 번호)
---------
1 2 3 4 5 (0번 회원의 각 치킨 선호도)
5 4 3 2 1 (1번 회원의 각 치킨 선호도)
1 2 3 2 1 (2번 회원의 각 치킨 선호도)
---------
012 3+5+3 (0-1-2번 치킨을 먹는 경우 각 회원의 최대 선호도를 더한 값)
013 4+5+2 (0-1-3번 치킨을 먹는 경우 각 회원의 최대 선호도를 더한 값)
014 5+5+2
023 4+5+3
024 5+5+3=13 (최대!)
034 5+5+2
123 4+4+3
124 5+4+3
134 5+4+2
234 5+3+3

0-1-2번 치킨을 먹는 경우
0번 회원은 0-1-2번에 대해 각각 1-2-3의 선호도를 가지며, 이 중 최대 선호도는 3이다.
1번 회원은 0-1-2번에 대해 각각 5-4-3의 선호도를 가지며, 이 중 최대 선호도는 5이다.
2번 회원은 0-1-2번에 대해 각각 1-2-3의 선호도를 가지며, 이 중 최대 선호도는 3이다.
따라서 합은 3+5+3=11이다.

치킨 3개를 고르는 모든 경우에 대해 이 과정을 진행하고 합의 최댓값을 구하면 된다.

profile
기록하는 개발자 👀

0개의 댓글