백준 2961 도영이가 만든 맛있는 음식 파이썬 문제풀이 (python 최적화, 재귀, 백트래킹 경우의 수)

728x90
반응형

 

 

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

문제는 n개의 재료가 들어오면 두 수 (신맛, 쓴맛)이 들어오는데,

신맛끼리는 곱하고, 쓴맛끼리는 더해서

신맛 곱과 쓴맛 합의 차가 최소인 요리를 구해서 값을 출력하는 문제이다.

 

즉 각 재료에 대해 쓸 것인지 아닌지를 구분해서 조합을 구하는 느낌인데,

재귀를 이용해서 구현해보자.

 

n = int(input())
ingre = []
answer = float('inf')
def recur(mul, sum, depth):
    global answer
    if depth == n:
        # 신맛 곱과 쓴맛 합의 차 구하기
        if answer > abs(mul - sum):
            answer = abs(mul-sum)
        return
    recur(mul*ingre[depth][0], sum+ingre[depth][1], depth+1)
    recur(mul, sum, depth + 1)

for i in range(n):
    s,b = map(int,input().split())
    ingre.append([s,b])
for i in range(n):
    recur(ingre[i][0], ingre[i][1], 1)
print(answer)

depth가 끝까지 갔을 때 조합한 재료로 곱과 합의 차를 구해서 작으면 넣는 식으로 구현했다.

예제 답은 잘 나오는데,

답은 틀렸다.

 

로직은 분명 맞는데 실수가 있는건가?

잘 보니 처음에 호출할 때 depth쪽에 실수가 좀 있었다.

정답코드

n = int(input())
ingre = []
answer = float('inf')
def recur(mul, sum, depth):
    global answer
    if depth == n:
        # 신맛 곱과 쓴맛 합의 차 구하기
        if answer > abs(mul - sum):
            answer = abs(mul-sum)
        return
    recur(mul*ingre[depth][0], sum+ingre[depth][1], depth+1)
    recur(mul, sum, depth + 1)

for i in range(n):
    s,b = map(int,input().split())
    ingre.append([s,b])
for i in range(n):
    recur(ingre[i][0], ingre[i][1], i+1)
print(answer)

for문으로 recur을 처음 호출할 때 아예 아무 재료도 넣지 않는 경우 때문에 이렇게 구현하였는데,

이때 depth를 1로 넣으면 안되고, 현재 ingre의 index를 depth로 넣어야했다.

 

맞았다~ 

728x90
반응형
  • 네이버 블로그 공유
  • 네이버 밴드 공유
  • 페이스북 공유
  • 카카오스토리 공유