[완전 탐색] 백준 16439 (파이썬) : 치킨치킨치킨

간단한 문제입니다. 선호도와 만족도의 관계를 조합을 바탕으로 이해하는 것이 관건이라고 할 수 있습니다. 

고리 회원과 메뉴가 몇 개든 상관없이 치킨은 세 가지 종류만 시킬 수 있습니다. 그래서 이를 조합으로 경우의 수를 나열하여 각 회원이 경우의 수로 선택된 메뉴에 대한 선호도 중 가장 높은 값이 해당 경우에 수에 대한 그 회원의 만족도가 되는 것입니다. 

 

from itertools import combinations
 
n,m = map(int,input().split()) 
prefer = [list(map(int,input().split())) for i in range(n)] 
result = 0
 
for combi in combinations(range(m),3): 
    satisfy_sum = 0                           
    for r in range(n):                
        p = 0
        for idx in combi:
            p = max(p,prefer[r][idx])     
        satisfy_sum += p                      
    result = max(result,satisfy_sum)          
print(result)

코드입니다. combinations 함수를 이용합니다. combinations는 말 그대로 조합을 나타냅니다. 예를 들어 A, B, C가 있고 이 중 2개를 고르는 combination을 구현할 때 print(combinations(A, B, C 중에서, 2)라고 입력하면 출력은 [('A','B'), ('A','C'), ('B','C')]가 나옵니다. 

 

먼저 예시 입력처럼 map과 split으로 공백을 기준으로 입력을 받아줍니다.

그 다음 선호도를 나타내는 prefer라는 리스트를 만들고 이를 회원의 수만큼 만들어줍니다.

result는 최종 만족도의 합을 나타내는 변수입니다.

 

밑의 과정은 문제의 예제 입력 1을 풀이하면서 설명하겠습니다.

먼저 입력에서 사람은 3명, 메뉴는 5개입니다. 여기 메뉴 중에서 3개를 뽑는 것입니다. 

그렇다면 입력 화면은 기준으로 세로가 메뉴이기 때문에 왼쪽부터 1, 2, 3, 4, 5번이라고 하면 가능한 경우의 수는 

(1,2,3) (1,2,4) (1,2,5) (1,3,4) (1,3,5) (1,4,5) (2,3,4) (2,3,5) (2,4,5) (3,4,5)입니다.

 

첫 번째 경우를 예로 들겠습니다.

1, 2, 3을 골랐을 때 안쪽 for문을 통해 봤을 때 첫 번째 회원의 선호도는 1, 2, 3으로 3이 가장 높습니다.

여기서 안쪽 for문을 벗어나 다음 사람으로 넘어갑니다. 

두 번째 사람은 선호도가 5, 4, 3이라서 5가 가장 높습니다. 세 번째 사람도 1, 2, 3으로 3이 가장 높습니다.

 

여기서 p는 위에서 회원별 최고 선호도 즉 만족도  3, 5, 3을 나타내고, satisfy_sum은 3+5+3을 하여 11입니다.

그리고 이 11이 첫 result로 저장이 됩니다. 그리고 경우의 수를 모두 반복하여 기존의 result보다 이번 경우의 수에서 나온 satisfy_sum이 더 크면 그 값으로 result를 대체하여 모든 경우의 수에서의 최댓값을 찾는 것입니다.

 

정답은 (1, 3, 5)의 경우로 첫 번째와 두 번째 회원의 만족도가 5, 세 번째 회원이 3이 나와 satisfy_sum이 13이 됩니다.