(BOJ)-2961, Python

문제 요약

출처: (BOJ)2961 - 도영이가 만든 맛있는 음식

재료의 개수($N$)가 주어지고, 각 재료의 신맛($S$), 쓴맛($B$) 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 것이 목표이다.

• 재료를 추가했을 때, 신맛은 곱으로, 쓴맛은 합으로 추가된다.
• 적어도 하나의 재료를 사용해야 한다.

접근 과정

1. 완전탐색 접근(For문)

문제를 처음 보자마자 느낀 점은, 반복문만으로는 해결할 수 없겠다는 것이었다. 주어진 재료를 사용할지 말지를 단순히 반복문으로 어떻게 표현해야 할지 감이 안 잡혔다..

2. 완전탐색 접근(재귀)

반복문으로 해결하려 했지만, 경우를 나눌 수 없다고 판단했다. 그래서 다음으로 떠올린 방법이 바로 재귀였다. 경우를 나눠 완전탐색을 할 방법으로 재귀만 떠올랐기에, 이를 바로 적용해 보았다. 아직 배운 것이 많지 않아 재귀 외에 다른 접근법은 생각하지 못했지만, 우선 시도해 보았고 아래와 같이 코드를 작성했다. 결과는 맞았다.

코드 구현

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

def recursion(idx, S, B, cnt):
    global gap
    
    if idx == N:
        if cnt > 0:
            gap = min(gap, abs(S-B))
            return 
        else:
            return    
    #재료를 사용하는 경우
    recursion(idx+1, S * arr[idx][0], B + arr[idx][1], cnt + 1)
    #재료를 사용하지 않는 경우
    recursion(idx+1, S, B, cnt)
  
gap = 1e9
recursion(0,1,0,0)  
print(gap)

회고

재귀를 이용하여 이 문제를 풀어보니 느낀 것은 완전탐색이지만, 구현방법만 다르다는 것이다. 모든 경우의 수를 탐색하는 것이 완전탐색의 본질인데, 반복문이나 재귀를 사용해도 모든 경우의 수를 탐색하는 것은 똑같다. 이전 포스트에서도 모든 경우의 수를 구하는 것이라고 언급은 했지만, 그냥 스킬로만 보았던 것 같다.