[백준 19942] 2020 정올 1차 중등부 "다이어트"

문제 출처 : https://www.acmicpc.net/problem/19942

19942번: 다이어트

이 문제는 2020년 정보올림피아드 1차 중등부 2번 문제 입니다.

문제 이해하기

단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 넘어서는 최소 가격을 찾으면 되는 문제 입니다.

N의 크기가 15로 비교적 작기 때문에 브루트 포스나 백트래킹으로 쉽게 결과를 찾을 수 있습니다. 백트래킹을 통해 문제를 해결해 보겠습니다. 백트래킹에 대해 잘 모른다면 아래 링크를 통해 백트래킹 기법이 무엇인지 확인 바랍니다.

https://wikidocs.net/206357

07. 백 트래킹

코드 작성하기

직접 코드를 작성하면서 문제를 해결해 보겠습니다.

입력 받기

N = int(input())

mp, mf, ms, mv = map(int, input().split())
INF = 10e9
mc = INF
foods = [0]

for i in range(N):
    tmp = tuple(map(int, input().split()))
    foods.append(tmp)

식재료의 개수 N을 입력 받습니다. 다음으로 단백질, 지방, 탄수화물, 비타민의 최소 영양 성분 mp, mf, ms, mv를 입력 받았습니다. 최소 가격을 찾는 것이기 때문에 최소 가격 mc의 초기값은 가장 큰 값으로 하였습니다.

그리고 N개의 줄에 단백질, 지방, 탄수화물, 비타민, 가격 5개의 값을 받아 foods라는 리스트에 넣었습니다. 이 때 foods에 0을 처음에 넣은 이유는 식재료의 번호는 1부터 시작하기 때문에 0을 넣어 입력값의 인덱스를 1번으로 하기 위해서 입니다.

결과 출력

ans = []
visited = []

f = [0, 0, 0, 0, 0]
solve(0, f)

if mc == INF:
    print(-1)
else:
    print(mc)
    print(*ans)

solve 라는 함수를 사용하여 결과를 출력해 줍니다. visited는 방문한 식재료를 확인하기 위한 리스트 입니다. ans는 최소 비용을 가지는 식재료 번호를 넣어두기 위해 만들었습니다. 최종적으로 가격인 mc가 INF라면 -1을 출력하고, 아니면 가격과 식재료 변호를 출력하도록 하였습니다.

solve 함수에 들어가는 인자는 크게 두 가지 입니다. 첫 번째는 현재 식재료를 어디까지 탐색했는지 나타내기 위한 것입니다. 두 번째 들어가는 인자는 총 5개의 값으로 이루어진 리스트로 현재까지 더해진 영양 성분 4가지와 가격 입니다.

solve 함수

def solve(num, food):
    global mc, ans

    if mp <= food[0] and mf <= food[1] and ms <= food[2] and mv <= food[3] and food[4] < mc:
        mc = food[4]
        ans = visited.copy()
    
    for idx in range(num + 1, N + 1):
        fd = foods[idx]
        for i in range(5):
            food[i] += fd[i]
        
        visited.append(idx)
        solve(food, idx)

        for i in range(5):
            food[i] -= fd[i]
        
        visited.pop()

핵심 함수인 solve 함수를 확인해 보겠습니다. 최소 가격 mc와 그 결과 리스트인 ans는 글로벌 변수로 두어 함수 안에서도 수정 가능하도록 하였습니다.

식재료의 4가지 성분이 기준치 보다 위에 있고 가격이 싸다면 mc와 ans에 저장되도록 하였습니다. visited.copy() 함수를 사용하여 저장한 이유는 이렇게 하지 않으면 visited와 연동되어 값이 계속 바뀌기 때문 입니다. 얕은 복사에 관한 내용으로 얕은 복사에 대해 잘 모른다면 아래 링크를 통해 얕은 복사가 무엇인지 확인 바랍니다. 이어 깊은 복사까지 공부하는 것이 좋습니다.

https://wikidocs.net/192439

02. 얕은 복사(Shallow copy)

이제 반복문을 통해 성분들을 계속 더해줍니다. 백 트래킹이기 때문에 방문이 끝나면 food의 성분에서 제외하고 방문 결과도 초기화 하면 됩니다.

전체 코드

N = int(input())

mp, mf, ms, mv = map(int, input().split())
INF = 10e9
mc = INF
ans = []
visited = []

foods = [0]
for _ in range(N):
    foods.append(tuple(map(int, input().split())))

def solve(num, food):
    global mc, ans

    if mp <= food[0] and mf <= food[1] and ms <= food[2] and mv <= food[3] and food[4] < mc:
        mc = food[4]
        ans = visited.copy()
    
    for idx in range(num + 1, N + 1):
        fd = foods[idx]
        for i in range(5):
            food[i] += fd[i]
        
        visited.append(idx)
        solve(food, idx)

        for i in range(5):
            food[i] -= fd[i]
        
        visited.pop()

f = [0, 0, 0, 0, 0]
solve(0, f)

if mc == INF:
    print(-1)
else:
    print(mc)
    print(*ans)