[백준] 2961 - 도영이가 만든 맛있는 음식 🍲 (Python) / 실버 2 / 브루트포스

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

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

문제

요약하자면, 재료의 개수 N이 주어지고, 다음 N개의 줄 동안 각 재료가 갖는 신맛과 쓴맛을 입력받습니다. 1개 이상의 재료를 사용했을 때 각 재료의 신맛은 모두 곱해지고, 쓴맛은 모두 더해집니다. 이 때, 신맛과 쓴맛의 차이가 가장 작을 때를 출력하면 됩니다.

 

1) 예제 입출력❄️

예제 입출력

재료가 1개일 때입니다. 해당 재료만 고르면 되고, 신맛은 3이고 쓴맛은 10입니다. 그 차이는 7이므로, 7을 출력합니다.

 

2. 핵심 논리☢️

재료의 신맛, 쓴맛을 이중리스트로 받습니다. 재료에 대해 1개~N개를 선택하는 combination을 모두 고려하여, 각각 신맛 쓴맛의 차이를 result에 min으로 갱신하는 것이 핵심입니다.

 

3. 풀이 코드✅

1) 코드

from itertools import combinations
N=int(input()) # 재료의 개수 입력
materials=[list(map(int,input().split())) for _ in range(N)] # 재료의 신맛, 쓴맛 이중 리스트
result=1e9 # 10억으로 초기화
for cmbs in [combinations(materials,i) for i in range(1,N+1)]:
    for c in cmbs:
        S,B=1,0       # 신맛, 쓴맛 초기화
        for s,b in c: # 각 조합에 대해
            S*=s;B+=b # 신맛은 곱하고, 쓴맛은 더한다
        result=min(result, abs(S-B)) # 최소값 갱신
print(result)

재료의 개수(N)을 입력받고, N번 반복하며 [신맛, 쓴맛]을 원소로 갖는 이중리스트 materials를 정의합니다. 최종 출력할 result를 10억(1e9)로 초기화 합니다. 그 이유는 처음에 문제에서 재료의 신맛과 쓴맛의 합은 최대 10억이라고 했는데, 그 차이는 그러면 10억 미만일 수 밖에 없기 때문입니다. 

 리스트컴프리헨션을 이용해 combinations에 대해 1개 선택하는 경우, ... N개 선택하는 경우를 모두 고려합니다. 각 조합에 대해 신맛과 쓴맛을 S와 B로 초기화 하고, cmbs를 c로 반복하며 신맛은 곱하고, 쓴맛은 더합니다. 해당 조합의 재료에 대해 신맛과 쓴맛의 차이는 abs(S-B)로 차이의 절대값을 구해줬습니다. 이를 result에 min으로 갱신하며 모든 경우에 대해 최소값이 result에 저장되도록 합니다.

 

읽어주셔서 감사합니다.

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

 

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

https://github.com/netsus/BaekJoon/blob/master/jupyter/2961_%EB%8F%84%EC%98%81%EC%9D%B4%EA%B0%80_%EB%A7%8C%EB%93%A0_%EB%A7%9B%EC%9E%88%EB%8A%94_%EC%9D%8C%EC%8B%9D.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

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