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
반응형
'개발 · 컴퓨터공학 > 알고리즘' 카테고리의 다른 글
백준 14501 퇴사 파이썬 문제풀이 (python 최적화, 재귀, 백트래킹 경우의 수) (8) | 2024.09.29 |
---|---|
백준 19942 다이어트 파이썬 문제풀이 (python 최적화, 재귀, 백트래킹 경우의 수) (13) | 2024.09.28 |
백준 2503 숫자야구 파이썬 문제풀이 (python 완전탐색, 재귀, 백트래킹) (12) | 2024.09.26 |
백준 15649 N과M 파이썬 문제풀이 (python 완전탐색, 재귀, 백트래킹) (15) | 2024.09.25 |
백준 3020 개똥벌레 파이썬 문제풀이 (python 누적합) (15) | 2024.09.24 |