백준 19942 다이어트 파이썬 문제풀이 (python 최적화, 재귀, 백트래킹 경우의 수)

click

 

백준 다이어트 파이썬 문제풀이

식재료 N개를 주면 이 중 한 개 이상의 재료를 선택해서 일정 영양성분 이상이 되는 조합을 찾는다.

그리고 영양분 조건을 만족하는 식재료 조합 중에서 최소 가격이 되는 것을 고르는 문제이다. 

 

재귀를 통해서 각 재료를 선택할지 말지에 대해

각각의 케이스에 따른 가지를 뻗어나간다.

 

영양분 조건을 만족하면서 최소 비용이 나오면 답으로 채택하고,

없다면 -1을 출력하도록 구현한다. 

 

n = int(input())
ingre = []
mp,mf,ms,mv = map(int,input().split())
minPri = float('inf')
answer = []
def recur(idx, pro, fat, cab, vit, pri, idxLst):
    global minPri, answer

    if idx == n:
        # 식재료 조건 만족
        if mp <= pro and mf <= fat and ms <= cab and mv <= vit:
            # 최소 비용
            if minPri > pri:
                minPri = pri
                answer = idxLst
        return
    recur(idx+1, pro+ingre[idx][0], fat+ingre[idx][1], cab+ingre[idx][2],
          vit+ingre[idx][3], pri+ingre[idx][4], idxLst+[idx])
    recur(idx+1, pro,fat,cab,vit,pri, idxLst)

# 식재료 준비 
for i in range(n):
    p,f,s,v,c = map(int, input().split())
    ingre.append([p,f,s,v,c])
recur(0, 0,0,0,0,0, [])
if len(answer) == 0:
    print(-1)
else:
    print(minPri)
    for l in answer:
        print(l+1,end=" ")

이렇게 식재료 조건과 최소비용을 재귀로 비교하면서 답을 구하고

출력한다.

 

99퍼까지 채점이 진행되었지만, 결과적으로는 틀렸다.

 

흠.. 아무것도 선택하지 않는 경우를 체크하지 않았었나?

 

반례

3
0 0 0 1
0 0 0 1 1
0 0 0 0 0
0 0 0 0 0

위 반례의 경우

1
1 2 3

이렇게 출력되는데 올바른 답은

1
1

이라고 한다.

모두 0인 재료가 있을 수 있고, 이런 경우 사용하지 않는 쪽이 출력되어야한다.

 

 

그러면 여기서 조건을 추가해주자.

n = int(input())
ingre = []
mp,mf,ms,mv = map(int,input().split())
minPri = float('inf')
answer = []
def recur(idx, pro, fat, cab, vit, pri, idxLst):
    global minPri, answer

    if idx == n:
        if len(idxLst) == 0:
            return
        # 식재료 조건 만족
        if mp <= pro and mf <= fat and ms <= cab and mv <= vit:
            # 최소 비용
            if minPri > pri:
                minPri = pri
                answer = idxLst
            elif minPri == pri:
                if answer > idxLst:
                    answer = idxLst
        return
    recur(idx+1, pro+ingre[idx][0], fat+ingre[idx][1], cab+ingre[idx][2],
          vit+ingre[idx][3], pri+ingre[idx][4], idxLst+[idx])
    recur(idx+1, pro,fat,cab,vit,pri, idxLst)

# 식재료 준비 
for i in range(n):
    p,f,s,v,c = map(int, input().split())
    ingre.append([p,f,s,v,c])
recur(0, 0,0,0,0,0, [])
if len(answer) == 0:
    print(-1)
else:
    print(minPri)
    for l in answer:
        print(l+1,end=" ")

답이 여러개인 경우

배열을 사전순으로 비교해서 더 앞이면 대입한다.

 

사전순 비교는 단순히 a>b 비교 방법을 사용하면 파이썬에서는 자동으로 비교해준다.

이 조건을 추가했더니

맞았다!~