https://www.acmicpc.net/problem/2961
solution) 모든 경우의 수를 따져서 계산하는 방법 사용
1. 입력 받아오기
n = int(input())
flavor = [list(map(int,input().split())) for _ in range(n)]
2. 재귀함수를 사용해 모든 경우의 수 따지기
- answer을 크게 설정해 신맛과 쓴맛의 차이가 가장 작은 요리 출력
def recur(idx, sour , bitter) :
global answer #재귀함수 밖에 있는 값 사용
if idx == n :
#신맛과 쓴맛의 차이
result = abs(bitter - sour)
#가장 작은 요리의 차이 업데이트
answer = min(answer,result)
return
#맛을 사용하는 경우
recur(idx+1 , sour * flavor[i][0] , bitter * flavor[i][1])
#맛을 사용하지 않는 경우
recur(idx+1, sour , bitter)
answer = 99999999
3.예외처리하기
- 재료는 적어도 하나를 사용해야 하기에 재료를 하나도 사용하지 않은 경우에는 출력 X
def recur(idx, sour , bitter, use) :
global answer #재귀함수 밖에 있는 값 사용
if idx == n :
#만일 아무맛도 사용하지 않았을 경우 결과 출력 X
if use == 0:
return
#신맛과 쓴맛의 차이
result = abs(bitter - sour)
#가장 작은 요리의 차이 업데이트
answer = min(answer,result)
return
#맛을 사용하는 경우(use + 1)
recur(idx+1 , sour * flavor[i][0] , bitter * flavor[i][1] , use+1)
#맛을 사용하지 않는 경우 (use)
recur(idx+1, sour , bitter, use)
answer = 99999999
4. 전체코드
def recur(idx , sour, bitter , use ) :
#재귀함수에서 밖에 있는 걸 사용할 경우 global사용
global answer
if idx == n :
if use == 0 : #아무재료도 사용하지 않았다면
return
result = abs(sour-bitter)
answer = min(answer , result)
return answer
recur(idx+1, sour*flavor[idx][0] ,bitter+flavor[idx][1] , use +1)
recur(idx+1 , sour, bitter ,use)
n = int(input())
answer = 999999999999999
flavor = [list(map(int,input().split())) for _ in range(n)]
recur(0,1,0,0)
print(answer)
'코딩테스트 (Coding Test)' 카테고리의 다른 글
다이나믹 프로그래밍 - 파이썬 (1) | 2023.10.05 |
---|---|
[백준] 14501번 퇴사 - 파이썬 (0) | 2023.10.04 |
[백준] 2503번 숫자야구 - 파이썬 (0) | 2023.10.03 |
기초 알고리즘 [정렬] (0) | 2023.09.27 |
기초 알고리즘 [수학] (0) | 2023.09.27 |