[백준] 16439 - 치킨치킨치킨 🍗 (Python) / 실버 4 / 브루트포스

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

링크: https://www.acmicpc.net/problem/16439

문제

문제를 요약하자면, N명의 회원들에 대해, M개의 치킨에 대해 선호도가 주어졌습니다. 3개의 치킨만 골라서, 각자 3개의 치킨 중에 선호도가 제일 높은 치킨의 선호도를 N명에 대해 만족도의 합이 최대가 되도록 출력해야 합니다.

 

1) 예제 입출력❄️

예제 입출력

예제 입력 1을 보면, 첫번째, 세 번째, 다섯 번째 치킨을 고른 경우, 첫 번째 회원(1행)의 만족도는 5번째 치킨의 만족도인 5이고, 두 번째 회원(2행)은 첫 번째 치킨의 만족도인 5이고, 세 번째 회원(3행)은 3번째 치킨의 만족도인 3으로 합이 13이 되며, 이게 만족도의 합중에 최댓값입니다.

 

2. 핵심 논리☢️

치킨의 종류에 대한 모든 3가지 combinations(조합)에 대해, 각 회원의 만족도 최댓값을 모두 탐색하는 브루트 포스 방법이 핵심 논리입니다.

 

3. 풀이 코드✅

1) 코드

from itertools import combinations

N,M=map(int,input().split()) # 회원수, 치킨 종류수 입력
like=[list(map(int,input().split())) for _ in range(N)] # 회원별 치킨 선호도 리스트
result=0

for comb in combinations(range(M),3): # 각 조합별로
    c_sum=0                           # 치킨 만족도의 합 저장할 변수
    for r in range(N):                # 각 회원별로
        p=0
        for idx in comb:
            p=max(p,like[r][idx])     # 치킨 만족도 최대값을 구해서
        c_sum+=p                      # 모두 더해 c_sum에 넣습니다.
    result=max(result,c_sum)          # 최대값 갱신
print(result)

N(회원 수)와 M(치킨 종류수)를 입력받습니다. 그리고 회원별 치킨의 선호도를 이중 리스트로 입력받아 like에 저장합니다. 그리고, 최종 출력할 result 변수를 0으로 초기화해줍니다. 다음으로 M개의 치킨에 대해 3개의 모든 조합을 combinations(range(M),3)로 구해줘서 각 조합을 comb로 반복합니다. 각 회원의 치킨 만족도 최댓값의 합을 저장할 변수 c_sum을 0으로 초기화 해주고, 조합별로 회원의 최대 만족도를 p에 저장합니다. (0으로 초기화하고, max로 최대값 갱신) 그 후 c_sum을 max로 갱신하며 result에 넣어 출력해주면 됩니다.

 

2) 숏 코딩

from itertools import combinations

N,M=map(int,input().split()) # 회원수, 치킨 종류수 입력
like=[list(map(int,input().split())) for _ in range(N)] # 회원별 치킨 선호도 리스트
result=0 # 출력할 결과

for a,b,c in combinations(range(M),3):
    m=sum(max(p[a],p[b],p[c]) for p in like) # 핵심
    result=max(result,m)
print(result)

위 코드보다 훨씬 간결해지고 가독성도 나쁘지 않습니다. 핵심은 like에서 각 person(p)를 반복하며 조합의 인덱스를 a, b, c로 받아와서 3개의 치킨 중 만족도의 최대를 max로 찾아주고, 그것을 바로 sum으로 묶어주는 것입니다. 여기서 리스트컴프리헨션 없이, sum으로 바로 묵어줄 수 있는 이유는 소괄호 자체로 컴프리헨션 구문을 묶어주는 것이 가능하기 때문입니다. 이는 제너레이트 컴프리헨션이라는 키워드로 개념을 찾아보실 수 있습니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/16439_%EC%B9%98%ED%82%A8%EC%B9%98%ED%82%A8%EC%B9%98%ED%82%A8.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/