[Python] 백준 2961: 도영이가 만든 맛있는 음식

문제 링크

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

문제 요약

도영이는 재료 N개로 요리를 만들려고 한다. 각 재료의 신맛과(S) 쓴맛(B)을 알고 있고, 요리의 신맛은 각 재료 신맛의 곱이고, 쓴맛은 합일 때, 신맛과 쓴맛의 차이의 최소값을 구하라.
※ 단, 요리를 완성하기 위해 재료는 1개 이상 사용하여야 한다.
※ N(1 ≤ N ≤ 10)이고, 모든 재료의 신맛과 쓴맛의 합은 1,000,000,000 작은 양의 정수이다.

 

풀이 설명

이 문제의 알고리즘 분류는 브루트포스, 비트마스킹, 백트래킹이었으나, 가지치기 조건을 찾지 못하여(떠올린 모든 가설 조건에 예외가 발생) 브루트포스 방식으로 해결하였다.

 

이 문제에서 1, 2, ..., N개의 재료를 선택하는 각 경우에 대해, 모든 경우를 탐색해야 하였으며, 이를 재귀 함수로 푸는 방법을 떠올려서 구현하였다. 

 

N=int(input())
ingredients=[]
for _ in range(N):
    S, B=map(int, input().split())
    ingredients.append((S, B))

flavor=999999999

# ...(중략)...

for k in range(1, N+1):
    for i in range(N-k+1):
        add_ingredient(1, 0, k, i)

print(flavor)

 

입력 사항들을 저장하고, 신맛과 쓴맛의 차이(flavor) 최솟값을 구하는 것이므로 초기 flavor는 입력값 제한에 따른 최대값인 999999999으로 설정하였다.

 

재귀함수는 다음과 같이 구성되어 있다.

add_ingredient(S, B, rest, next_ingredient)

S는 신맛, B는 쓴맛, rest는 맛에 반영되어야 하는 남은 재료 수를 의미하며, next_ingredient는 ingredients 리스트를 기준으로 다음에 넣을 재료의 index를 의미한다.

def add_ingredient(S, B, rest, target_ingredient):
    global flavor
    cur_S, cur_B=ingredients[target_ingredient]
    cur_S*=S
    cur_B+=B
    rest-=1
    if rest==0:
        cur_flavor=abs(cur_B-cur_S)
        flavor=min(flavor, cur_flavor)
        return 0
    elif rest>0:
        for i in range(target_ingredient+1, N-rest+1):
            add_ingredient(cur_S, cur_B, rest, i)

 

flavor을 global variable로 두고, 위의 함수와 같이 rest==0이면, 해당 값을 업데이트한다.

rest>0인 경우에는 현재 target_ingredient+1인 index부터 N-rest+1 까지의 i에 한해 다음 재귀함수를 넣음으로써 ingredient가 의도치않게 추가되지 않는 사례를 방지하였다.

 

마찬가지로 처음 재귀함수 실행시키는 본문에서도 N-k+1까지 범위를 지정함으로써 의도한 갯수의 ingredient가 flavor에 반영되게끔하였다. (이렇게 범위를 명확히 주지 않으면 코드에 따라 indexError도 발생할 수 있다.)

 

여기까지 재귀 함수로 푼 나의 방식이었고, 다른 사람들의 풀이 방식을 살펴보니 내가 떠올리지 못했던 신기한 방식이 있었다.

비트 마스킹 방식의 풀이 설명

import sys
input = sys.stdin.readline

#...(중략)...

n=int(input())
tastes = []
for _ in range(n):
    s,b = map(int,input().split())
    tastes.append((s,b))
solution(n,tastes)

dasapcr 유저분의 풀이인데,

핵심적인 solution 함수 내용을 제외한 답 코드는 위와 같다.

나와 마찬가지로 tuple 자료형으로 S, B를 엮어서 list에 저장하셨다.

 

def solution(n,tastes):
    if n==1:
        print(abs(tastes[0][0]-tastes[0][1]))
        return
    else:
        result = sys.maxsize
        for i in range(1,2**n):
            sum1,sum2 = 1,0
            for j in range(n):
                if (i & 1 << j) != 0:
                    sum1 *= tastes[j][0]
                    sum2 += tastes[j][1]
            result = min(result,abs(sum1-sum2))
        print(result)
        return

 

i는 2진수로 간주되어서, n개 재료의 모든 경우의 수를 표현할 수 있다.

예를 들어 00001001이면 5번째와 8번째 재료가 들어가는 요리라는 방식으로 해석한다.

 

비트 AND 연산자(&)와 비트 left shift 연산자(<<) 중 shift 연산자의 우선순위가 높아 먼저 반영되는데, 실무에서는 명확하게 괄호로 연산의 우선순위를 나타낸다고 한다.

 

 

원큐에 풀어서 기분이 좋았으나, 다시 풀이를 검토하는 과정에서 내 풀이의 취약점일 수 있는 요소들을 파악하였고 이를 재확인할 수 있었다. (오답을 도출하는 요소는 아니었고, 소요 시간을 다소 늘릴 수 있는 비효율적인 요소를 개선하였다.)