[알고리즘] BOJ 2961번 - 도영이가 만든 맛있는 음식(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

9 / 50

 

탐색

10 / 50(NEW!)

 

기초 동적 프로그래밍

7 / 50

---

투포인터

2 / 10

 

이분탐색

0 / 10

---

문제

2961번: 도영이가 만든 맛있는 음식

→ solved.ac 기준 실버 2

---

문제 해결 아이디어

재료의 수가 적기 때문에 브루트포스로 풀어도 충분히 가능한 문제.

1부터 n까지 조합으로 모든 경우를 알아낸 후 answer를 업데이트

→ 다만 비트마스킹 공부한다고 푼 문제여서 비트마스킹으로 해결해보면,

1부터 n까지 조합을 만든다 == 부분집합을 만든다와 같으므로

비트마스킹을 사용해서 부분집합을 만들자.

---

구현

내 풀이: 비트마스킹 사용 X

import sys
from itertools import combinations
input = sys.stdin.readline
MAX = 1e9

n = int(input())
ingres = [tuple(map(int, input().split())) for _ in range(n)]

answer = MAX
for i in range(1, n + 1):
  cases = combinations(range(n), i)
  for case in cases:
    s = 1
    b = 0
    for j in range(len(ingres)):
      if j in case:
        s *= ingres[j][0]
        b += ingres[j][1]
    answer = min(answer, abs(s - b))

print(answer)

 

비트마스킹 사용

 

import sys
input = sys.stdin.readline
MAX = 1e9

n = int(input())
ingres = [tuple(map(int, input().split())) for _ in range(n)]

answer = MAX
for set in range(1, 1 << n):
  s = 1
  b = 0
  for j in range(n):
    if (set & (1 << j)) != 0:
      s *= ingres[j][0]
      b += ingres[j][1]
  answer = min(answer, abs(s - b))
print(answer)

---

메모

• 걸린 시간: 20분
  
  • 처음 풀이만. 비트마스킹은 학습하면서 했으므로 제외
• 처음 풀이와 두 번째 풀이 비교
  • 시간 면에서 4ms 차이

---

마치며

비트마스킹 문제는 처음 풀어보는데 아직은 어려운 듯..

몇 개 더 풀어보자!!