KOI 1차 2020 중2- 다이어트 > 문제은행 : 정보올림피아드&알고리즘




4521 : 다이어트

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
54 회   
시도횟수
132 회   

문제

식재료 N개 중에서 몇 개를 선택해서 이들의 영양분 (단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되도록 해야 한다.
아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택하여 이들의 영양분(단백질, 지방, 탄수화물, 비타민)의 각각 합이 최소 (100, 70, 90, 10)가 되도록 하는 경우를 생각해보자.

이 경우 모든 재료를 선택하면 쉽게 해결되지만 우리는 조건을 만족시키면서도 비용이 최소가 되는 합리적인 선택을 해야 한다.

예를 들어 식재료 {1, 3, 5}를 선택하면 영양분은 (100, 145, 130, 10)으로 조건을 만족하지만 가격은 270이 된다.

대신 {2, 3, 4}를 선택하면 영양분의 합은 (110, 130, 90, 10), 비용은 180이 되므로 앞서의 {1, 3, 5} 보다는 더 나은 선택이 된다. 여러분은 주어진 식재료 표에서 제시된 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

 재료

 단백질

 지방

 탄수화물

 비타민

 가격

 1

 30

 55

 10

 8

 100

 2

 60

 10

 10

 2

 70

 3

 10

 80

 50

 0

 50

 4

 40

 30

 30

 8

 60

 5

 60

 10

 70

 2

 120

 6

 20

 70

 50

 4

 40



입력형식

입력의 첫 줄에는 식재료의 개수를 뜻하는 정수 N(3≤N≤15)이 주어진다.

 

다음 줄에는 최소 영양성분을 나타내는 정수 mp, mf, ms, mv가 주어진다. (0≤​mp,mf,ms,mv≤​500, mp+mf+ms+mv>0)

이어지는 N개의 각 줄에는 i번째 식재료의 영양분과 가격이 5개의 정수로 pi, fi, si, vi, ci와 같이 주어진다. (실제 입력에는 콤마 대신 빈칸을 사이에 두고 있다.) 이 값들은 0 이상 500 이하의 정수이다.


출력형식

여러분은 첫 번째 줄에 최소 비용을 출력하고, 두 번째 줄에 조건을 만족하는 최소 비용 식재료의 index를 오름차순으로 한 줄에 출력해야 한다.

같은 비용의 집합이 하나 이상이면 사전식으로 가장 빠른 것을 출력한다.

index는 1부터 센다.

 

만약 답이 없으면 첫 번째 줄에 -1을 출력하고, 두 번째 줄에 아무것도 출력하지 않는다.

 


입력 예

6
100 70 90 10
30 55 10 8 100
60 10 10 2 70
10 80 50 0 50
40 30 30 8 60
60 10 70 2 120
20 70 50 4 4

출력 예

134
2 4 6

데이타 만든사람 : ohjtgood

백트래킹, Brute Force

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP