[Python 3] BOJ 19942 다이어트

 

영양분 (단백질, 탄수화물, 지방, 비타민)이 일정 기준 이상 갖춰지게끔 하는 식재료들의 조합 중 가장 가격이 싼 경우를 정하는 문제였다. 만약 가격이 가장 싼 경우가 한 가지가 아닐 경우, 사전 순으로 가장 빠른 경우를 출력하는 문제였다.

---

 

Brute Force와 Backtracking을 이용하여 해결하였다.

 

DFS를 이용해 반복적인 backtracking을 통해 모든 경우에 대한 brute force를 할 수 있었다.

시간 복잡도는 O(2^n)이지만, n의 크기가 최대 15이기 때문에 파이썬으로도 충분히 시간 제한 내에 들어올 수 있다.

 

flag variable을 이용하여 영양소 최저 기준을 모두 만족하였는지 확인한다.

만약 영양소 최저 기준을 만족했다면, 정답으로 들어올 수 있는지 확인한다.

여기서 기존 가격보다 더욱 저렴하게 조합을 완성할 수 있으면, 새로운 조합으로 정답을 바꾼다.

하지만, 같은 경우에는 사전 순으로 어떤게 먼저 앞으로 오는지 확인해보아야 한다!!

이 부분에서 저절로 처리가 될 것이라고 생각했는데, 재귀를 사용하고 있기 때문에 무조건적으로 해당 조건이 만족되지 않는다!!! 직접 해주어야 한다.

 

이후 해당 depth의 식재료를 사용하지 않는 경우와, 식재료를 사용해서 curr과 status를 업데이트 해주고, dfs를 돌렸다. 

n=int(input())
limits=list(map(int,input().split()))
data=list(list(map(int,input().split())) for _ in range(n))
answer=1e10
answerlist=[]
def dfs(status,curr,depth,price):
    global answer,answerlist
    flag=1
    for i in range(4):
        if status[i]<limits[i]:
            flag=0
            break
    if flag:
        if answer>price:
            answer=price
            answerlist=curr[:]
        elif price == answer and curr < answerlist:
            answerlist = curr[:]
        return
    if depth>=n:
        return
    dfs(status,curr,depth+1,price)
    for i in range(4):
        status[i]+=data[depth][i]
    curr.append(depth)
    dfs(status,curr,depth+1,price+data[depth][4])
    curr.pop()
    for i in range(4):
        status[i]-=data[depth][i]
dfs([0,0,0,0],list(),0,0)
if answer==1e10:
    print(-1)
    exit(0)
print(answer)
print(*list(map(lambda x:x+1,answerlist)))

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