BOJ(백준) 19942[다이어트]

1. 문제 설명

1) 도영이는 여러 재료를 이용해 음식을 만들고자 합니다.

2) 각 재료는 일정한 영양소를 가지고 있으며, 도영이는 이 재료들을 사용해 특정한 최소 영양소 요구조건을 만족시키면서 최소 비용으로 음식을 만들고자 합니다.

3) 이때, 최소 비용을 구하는 프로그램을 작성하세요.

 

문제 URL: https://www.acmicpc.net/problem/19942

 

2. 접근법

1) 입력받기: 재료의 수와 각 재료의 영양소 및 가격을 입력받습니다.

2) 재귀 함수 정의: 모든 재료를 사용했을 때의 영양소와 비용을 재귀적으로 계산하여 최소 비용을 구합니다.

3) 결과 출력: 가능한 최소 비용과 그에 해당하는 재료들의 인덱스를 출력합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력 처리
N = int(input())  # 재료의 개수
p, f, s, v = map(int, input().split())  # 최소 필요 영양소 (단백질, 지방, 탄수화물, 비타민)
igd = [list(map(int, input().split())) for _ in range(N)]  # 각 재료의 영양소와 가격 정보

# 초기값 설정
vol = sys.maxsize   # 최소 비용을 저장할 변수, 초기값은 매우 큰 값으로 설정
ansIgd = []         # 최소 비용을 만족하는 재료들의 인덱스를 저장할 리스트
locIgd = []         # 현재 재귀 호출에서 선택된 재료들의 인덱스를 저장할 리스트

# 재귀 함수 정의
def rec(idx, mp, mf, ms, mv, mVol):
    global vol
    global ansIgd
    global locIgd

    # 현재까지의 영양소와 비용이 최소 조건을 만족하고 비용이 최소일 경우 갱신
    if mp >= p and mf >= f and ms >= s and mv >= v and vol > mVol:
        vol = mVol
        ansIgd = locIgd.copy()  # 현재 선택된 재료들로 갱신
    
    # 모든 재료를 다 확인한 경우 재귀 종료
    if idx == N:
        return

    # 현재 재료를 선택하는 경우
    locIgd.append(idx+1)
    rec(idx+1, mp + igd[idx][0], mf + igd[idx][1], ms + igd[idx][2], mv + igd[idx][3], mVol + igd[idx][4])

    # 현재 재료를 선택하지 않는 경우
    locIgd.pop()
    rec(idx+1, mp, mf, ms, mv, mVol)

# 재귀 함수 호출 초기값 설정
rec(0, 0, 0, 0, 0, 0)

# 결과 출력
if len(ansIgd) > 0:
    print(vol)
    print(*ansIgd)
else:
    print(-1)

 

4. 코드 설명

1. 입력값 받기

• 재료의 수와 각 재료의 영양소와 가격을 입력받습니다.

2. 재귀 함수 정의

• 재귀 함수를 정의하여 모든 재료를 사용했을 때의 영양소와 비용을 계산하고 최소값을 갱신합니다.

3. 재귀 함수 호출

• 재귀 함수를 초기값으로 호출하여 계산을 시작합니다.

4. 결과값 출력

• 최종적으로 계산된 최소값을 출력합니다.

 

*** 아래와 같은 방법으로 코드를 작성하면 통과를 하지 못하게 된다......

# 모든 재료를 다 확인한 경우 재귀 종료
if idx == N:
    # 현재까지의 영양소와 비용이 최소 조건을 만족하고 비용이 최소일 경우 갱신
    if mp >= p and mf >= f and ms >= s and mv >= v and vol > mVol:
        vol = mVol
        ansIgd = locIgd.copy()  # 현재 선택된 재료들로 갱신
    return

 

idx가 끝에 도달하지 않아도 정답 조건을 만족하면 정답을 업데이트 하고 처리를 하지만

위와 같이 쓴 코드는 반드시 마지막 idx에 도달하도록 조건이 걸려 있기 때문에,

영양소가 없는 재료 가 있다는 가정 하에 아래와 같이 다른 결과가 나오게 됩니다.

[반례]

3

0 0 0 1

0 0 0 1  1

0 0 0 0 0

0 0 0 0 0

 

[정답코드]

비용 1, 재료선택 1

[오류코드]

비용 1, 재료선택 1,2,3 

 

5. Github으로 확인

coTest/BOJ/BOJ01_05_02_19942.py at main · pcy4196/coTest