완전탐색(유형정리) - 백준 16439

16439번: 치킨치킨치킨 (acmicpc.net)

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) 가 주어집니다.

출력

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

예제 입력 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

 

이번 문제는 이차원 배열 형식으로 입력받은 리스트 내부에서 3개씩 뽑아 만든 수 중에서 가장 큰 합을 찾는 문제라고 볼 수 있다. 일단, 3개씩 뽑아야 하는 문제이므로 combinations를 사용하면 간단하게 해결할 수 있을 것이라고 생각했다.

 

 

※ 알고리즘

1. 먼저 N, M을 입력받는다.

2. 선호도를 담을 리스트를 초기화 시킨 후 N개 만큼 반복문을 돌리면서 입력받는 새로운 리스트를 append 시켜준다.

3. combinations를 사용하여 M개 범위에서 3개를 뽑아 a, b, c에 담아준다.

4. count 변수에 뽑은 3개의 숫자의 max를 비교하여 담아준다.

5. 반복문 속에서 완전탐색을 통해 max가 되는 maxsum과 4번 과정을 통해 얻은 count의 수를 비교하여 max가 되는 합을 도출한다.

 

from itertools import combinations

N, M = map(int, input().split())

chicken_like = []

for i in range(N):
    chicken_like.append(list(map(int, input().split())))

maxsum = 0
for a,b,c in combinations(range(M), 3):
    count = 0
    for i in range(N):
        count += max(chicken_like[i][a],chicken_like[i][b],chicken_like[i][c])

    maxsum = max(maxsum, count)

print(maxsum)

 

이처럼 해결할 수 있다. 솔직히 combinations를 import 하지 않으면 3중 for문으로 하나하나 비교를 해주어야 하므로 오히려 모듈을 import 하는 것 보다 시간복잡도가 더 걸릴 것으로 생각하여 combinations를 사용했다.

또한, 초반에 입력 받는 단계에서 리스트 속의 리스트라는 것을 생각하지 못하여 계속해서 오류를 범하고 있던 문제였다.

 

백준 특유의 입력받는 방식의 복잡성에 대한 이해, combinations를 사용하여 조합을 하는 수학적 사고가 필요한 문제였다