1346: [KOI 2020 1차]다이어트(중등부 2번)
[만든사람 : KOI(2020)]
문제 설명
모든 언어에 대해 시간 제한 2초, 메모리 제한 512MB입니다.
식재료 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 이하의 정수이다.
다음 줄에는 최소 영양성분을 나타내는 정수 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을 출력하고, 두 번째 줄에 아무것도 출력하지 않는다.
입력 예시 Copy
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
출력 예시 Copy
134
2 4 6
도움
- 본 온라인 채점시스템에서는 KOI 공식 채점 데이터 중 일부에 대해서만 채점이 이루어집니다.
- 공식 문제와 전체 채점 데이터는 한국정보올림피아드(KOI)를 통해서 제공됩니다.
- 한국정보올림피아드(KOI) 공식 사이트 : https://koi.or.kr/
- 한국정보올림피아드(KOI) 공식 채점시스템 : https://oikorea.org/