[백준] 19942번 다이어트

사용 언어 - Python3

문제 -  19942번 다이어트

https://www.acmicpc.net/problem/19942

19942번: 다이어트

 

 

정답

재귀함수 문제

def recur(idx, p, f, s, v, price)

recur(인덱스수, 단백질, 지방, 탄수화물, 비타민, 사용한 비용합)

최소 영양성분 만족 + 현재의 answer보다 더 작은 price인 경우가 있다면,

answer를 최소값으로 업데이트해주고, 그때의 used를 answer_used에 저장해준다.

 

모든 인덱스 다 사용했다면, return

 

인덱스 한개씩 늘려가면서 반복해주기

used 사용한 재료인덱스 번호 추가해주기

- 해당 재료 사용 했다면, 각 영양분 합해주기

- 해당 재료 사용 안했다면, 각 영양분 값 그대로

 

answer_used 있는 경우, print(answer), print(*answer_used)

없는 경우, -1 출력

def recur(idx,p,f,s,v,price):
    global answer
    global used
    global answer_used
    
    if p >= mp and f >= mf and s >= ms and v >= mv: # 최소값 만족
        if answer > price: # 최소 비용이라면
            answer = min(answer,price)
            answer_used = []
            for i in used:
                answer_used.append(i)
    if idx == n:
        return
        
    used.append(idx+1) # 사용한 재료 추가
    # 재료 사용했다면        
    recur(idx+1, p+list_a[idx][0], f+list_a[idx][1], s+list_a[idx][2], v+list_a[idx][3], price+list_a[idx][4])
    used.pop() # 사용한 재료 삭제
    # 재료 사용안했다면
    recur(idx+1, p, f, s, v, price)
    
# 식재료 개수
n = int(input())
# 단백질, 지방, 탄수화물, 비타민의 최소 영양성분
mp,mf,ms,mv = map(int,input().split())
# 각 식재료의 단백질, 지방, 탄수화물, 비타민, 가격
list_a = [list(map(int,input().split())) for _ in range(n)]
answer = 1e9
used = [] # 사용한 재료
answer_used = [] # 최소값 만족하는 사용한 재료

recur(0,0,0,0,0,0)
answer_used.sort() # 정렬 후 프린트
if answer_used:
    print(answer)
    print(*answer_used)
else:
    print(-1)

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/19942_%EB%8B%A4%EC%9D%B4%EC%96%B4%ED%8A%B8.py