(BOJ)-19942, Python

문제 요약

출처: (BOJ)19942 - 다이어트

재료의 개수($N$)와 최소 영양소 기준이 주어졌을 때, 각 재료의 영양소 정보(탄수화물, 단백질, 지방, 비타민)와 가격을 활용해, 최소 영양소 기준을 만족하면서도 비용이 최소가 되도록 재료 선택을 하는 것이 목표이다.

• 조건에 만족하는 답이 없다면 $-1$ 출력
• 최소 비용을 가진 경우가 두 가지 이상이라면, 사전 순으로 빠른 것을 출력
  • $[1, 2 ,4], [1, 2, 5]$라면 $[1, 2, 4]$ 선택

접근 과정

1. 완전탐색 접근(For문)

문제를 처음 보자마자 느낀 점은, 이전포스트랑 크게 다른 게 없다는 것이다. 마찬가지로 재료를 사용할지 말지 경우를 나누는 문제에선 For문으로는 한계가 있다고 생각했다.

2. 완전탐색 접근(재귀)

다음으로, 재료를 사용하는 경우와 사용하지 않는 경우로 나누기 위해 재귀를 활용하여 접근하기로 했다.

코드 구현

#제출한 코드 

N = int(input())
a_, b_, c_, d_ = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

def recursion(idx, A, B, C, D, cost, use_idx):
    global price, result_idx
    if idx == N:
        if A >= a_ and B >= b_ and C >= c_ and D >= d_:
            if price > cost:
                price = cost
                result_idx = use_idx[:]
            elif price == cost:
		# i = 0 
		# 두 결과의 원소에 대해 순차적으로 비교를 진행
                # while len(result_idx) > i and len(use_idx) > i: 
                #     if result_idx[i] > use_idx[i]:
                #         result_idx = use_idx[:]
                #         break
                #     elif result_idx[i] < use_idx[i]:
                #         break
                #     else:
                #         i+= 1
                # #검사한 인덱스의 원소가 모두 같다면, 길이가 더 짧은 것을 선택
                # if len(result_idx) > len(use_idx): 
                #     result_idx = use_idx[:] 
                
                if result_idx > use_idx: #사전순 비교
                    result_idx = use_idx[:]    
        return 
    
    #재료를 사용하는 경우
    use_idx.append(idx+1)
    recursion(idx + 1, A + arr[idx][0], B + arr[idx][1], C + arr[idx][2], D + arr[idx][3], cost + arr[idx][4], use_idx)
    use_idx.pop()
    #재료를 사용하지 않는 경우
    recursion(idx + 1, A, B, C, D, cost, use_idx)
	
price = 1e9
result_idx = []
use_idx = []
recursion(0, 0, 0, 0, 0, 0, use_idx)

if result_idx:
    print(price)
    print(*result_idx)
else:
    print(-1)    

회고

재귀를 이용해서 접근은 할 수 있었지만, 사전순으로 출력이라는 조건에서 시간을 꽤 많이 보냈다. 반례라고 생각되는 조건으로 모든 영양소와 가격이 0인 재료가 포함된 경우도 고려해보고 작성했는데, 결과는 틀렸다고 나왔다. 이를 해결할 방법을 찾아보다가 알게된 사실은 두 리스트를 단순하게 비교연산(<,>,=)으로 사전순 비교가 가능하다는 것이다.. 허무하지만, 알게 된 것에 감사하기로 했다.