[코딩테스트][백준] 🔥 백준 19942번 "다이어트" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 15분

N=int(input())
ingredients=[]
k=list(map(int,input().split()))
for _ in range(N):
    ingredients.append(list(map(int,input().split())))

answer=1e9
answerList=[]
for i in range(1<<N):
    sumList=[0]*4
    cost=0
    numList=[]
    for j in range(N):
        if i&(1<<j):
            for t in range(4):
                sumList[t]+=ingredients[j][t]
            cost+=ingredients[j][4]
            numList.append(j+1)
    
    passed=True
    for t in range(4):
        if sumList[t]<k[t]:
            passed=False
            break
    if not passed:
        continue
    # print(cost,sumList,numList)
    if answer>cost:
        answer=cost
        answerList=[]
        answerList.append(" ".join(map(str,numList)))
    elif answer==cost:
        answerList.append(" ".join(map(str,numList)))
if len(answerList)==0:
    print(-1)
else:
    answerList.sort()
    print(answer)
    print(answerList[0])

식재료 조합 최적화 문제! 🍽️🔍

식재료 중에서 일정 식재료의 조합으로 기준점의 영향소를 넘기고 가격을 최소로 하는 부분집합을 찾는 문제이다. 그렇기 때문에 단순히 비트마스킹을 이용한 부분집합으로 풀 수 있다.

비트마스킹으로 모든 경우를 따지며 각 영향소들의 합을 따로 저장해주고 그 영향소를 기준과 비교해준다. 만약 기준을 통과한다면 정답으로써 갱신시킨다. 이 때, 조합 중에 가장 사전순으로 빠른 것을 출력해야 하므로 그냥 문자열로 변환해서 그 조합을 저장해두었다. 이 조합을 담은 배열을 정렬하여 가장 앞에 것을 출력하거나 이 정답 배열이 비어있다면 -1을 출력하면 된다.

이렇게 Python으로 백준의 "다이어트" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊