백준 2961. 도영이가 만든 맛있는 음식

도영이가 만든 맛있는 음식( https://www.acmicpc.net/problem/2961)

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. 

예제 입력 1 

1
3 10

예제 출력 1 

7

예제 입력 2 

2
3 8
5 8

예제 출력 2 

1

---

[체크 포인트]

1. 재료(N)의 최대가 10이다. -> 모든 조합을 시도해봐도 시간초과 날 일 없을 것 같다! -> 재귀를 써볼까?

2. 신맛은 곱, 쓴맛은 합임에 주의하자. -> 신맛은 1, 쓴맛은 0으로 초기화한다.

3. 재료는 적어도 하나 이상 사용해야한다. -> 재료를 하나도 사용하지 않는 경우를 제외(예외처리)한다.

---

[첫 번째 풀이]

def back(idx, sour, bitter, use):
    global ans

    if idx == N: # 모든 재료를 다 돌았을 때
        if use == 0: # 재료를 하나도 사용하지 않은 경우
            return
        else:
            ans = min(abs(sour - bitter), ans) # 최솟값 갱신
            return

    back(idx+1, sour * ingre[idx][0], bitter + ingre[idx][1], use+1) # 재료를 사용한 경우
    back(idx+1, sour, bitter, use) # 재료를 사용하지 않은 경우

N = int (input()) # 재료 개수
ingre = [list(map(int,input().split())) for _ in range(N)]
ans = 999999 

back(0,1,0,0)
print(ans)

[첫 번째 풀이 해설]

먼저 백트래킹을 이용해 재료를 사용한 경우, 사용하지 않은 경우로 나눠 함수를 호출시킨다.

백트래킹 함수(back)의 요소는 총 4가지이다. ( idx, sour, bitter, use )

- idx는 재료를 몇 개 탐색했는지 저장하는 변수다. 재료 사용 여부와 상관없이 +1을 해줘서 탐색 횟수를 기록한다. 초깃값은 0

- sour은 여태까지 고른 재료들의 신 맛의 곱이다. 초깃값은 1

- bitter은 여태까지 고른 재료들의 쓴 맛의 합이다. 초깃값은 0

- use는 아무 재료도 사용하지 않을 경우를 제외하기 위한 변수로, 재료를 몇 개 사용했는지 저장한다. 따라서 재료를 사용할 때마다 +1을 해준다. 초깃값은 0

재료를 사용한 경우에는 sour에 해당 재료의 신맛을 곱하고, bitter에 해당 재료의 쓴맛을 더한뒤, idx와 use를 1씩 증가시킨다.

재료를 사용하지 않은 경우에는 idx만 1 증가시키고 나머지는 그대로 둔다.

그렇게 idx가 재료의 개수인 N이 되어 재귀가 끝나면 재료를 하나도 사용하지 않은 경우를 제외한 후 두 맛의 차이의 최솟값을 갱신시킨다.

[두 번째 풀이]

def dfs(depth, start): # depth는 현재까지 뽑은 개수(무한방지) start는 현재 뽑을 수 있는 재료의 시작위치(중복방지)
    global res

    if depth == pick:  # 만약 깊이가 뽑을 개수와 같다면(len_개 만큼 뽑았다면)
        sour = 1  # 곱하기니까 초기값은 1
        bitter = 0  # 더하기니까 초기값은 0

        # 뽑은 모든 재료들 다 더하고 곱해주기
        for i in arr:
            sour *= i[0]
            bitter += i[1]

        if res > abs(bitter - sour):  # 최솟값 갱신
            res = abs(bitter - sour)
        return

    for i in range(start, N):
        arr.append(ingre[i])
        dfs(depth + 1, i + 1) # 하나 뽑을 때마다 depth와 i가 하나씩 증가
        arr.pop() # 하나 뽑기 전으로 돌리기


N = int(input())
ingre = [list(map(int, input().split())) for i in range(N)]
arr = []
res = 99999999  # 결과값을 처음에 아주 큰 값으로 초기화

for i in range(1, N + 1):  # 1~N 개까지 뽑아서 비교한다.
    pick = i
    dfs(0, 0)

print(res)

[두 번째 풀이 해설]

dfs 함수를 만들어 재귀를 시키는 방법이다. 이번엔 재료를 몇 개 뽑을 것인지에 초점을 맞춰 진행한다.

재료는 최소 1개부터 N개까지 뽑을 수 있으니 모든 경우의 수를 탐색한다. pick 변수는 재료를 뽑은 개수를 뜻한다.

dfs 함수에는 매개변수가 depth(여태 뽑은 개수)랑 start가 들어간다.

start는 현재 뽑을 수 있는 재료의 시작위치를 뜻하므로, 재료를 뽑을 때마다 1씩 증가시켜 중복을 방지한다.

전역변수 arr(초깃값은 빈 리스트)를 이용해 append(재료뽑음) -> dfs함수 호출 -> pop(재료뺌)을 반복하며,

depth가 뽑을 개수가 되었다면 sour과 bitter를 선언해주고 arr에 있는 모든 재료들의 신맛과 쓴맛을 누적곱,합 해준다.

그리고 두 맛의 차이를 최솟값 갱신해주며 마무리한다.