백준 2961번 파이썬 문제풀이(도영이가 만든 맛있는 음식)

---

간단한 dfs 문제이다. 단, 조합이므로 dfs의 약간 응용버전이라고 생각하면 된다. 2가지 방식으로 풀어봤다.

 

1. 템플릿

def dfs(depth, start):
    global result
    # 기저
    if depth == len_:  # 만약 깊이가 뽑을 개수와 같다면(len_개 만큼 뽑았다면)
        lemon = 1  # 신맛
        bad = 0  # 쓴맛
        for i in arr:  # 뽑은 신맛 쓴맛을 계산한다.
            lemon *= i[0]  # 신맛 값들을 곱해준다.
            bad += i[1]  # 쓴맛 값들을 더해준다.
        if abs(bad - lemon) < result:  # 만약 그 차가 저장된 값보다 적다면
            result = abs(bad - lemon)  # 그 차를 결과에 저장
        return  # 그 후 재귀 종료
    # 재귀
    for i in range(start, N):
        arr.append(cuisine[i])
        dfs(depth + 1, i + 1)
        arr.pop()


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

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

print(result)

 

2. 위의 템플릿 응용

def dfs(depth, cnt, lemon, bad):
    global result

    # 가지 치기
    if cnt != 0:
        if abs(lemon - bad) < result:
            result = abs(lemon - bad)

    # 기저
    if depth == N:
        return

    # 재귀
    dfs(depth + 1, cnt + 1, lemon * cuisine[depth][0], bad + cuisine[depth][1])  # 깊이와 개수 모두 증가시켜준다.
    dfs(depth + 1, cnt, lemon, bad)  # 깊이만 증가시키고 개수는 증가시키지 않는다.


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

dfs(0, 0, 1, 0)

print(result)