문제

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

식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해보자. 이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 한다.

재료	단백질	지방	탄수화물	비타민
1	30	55	10	8
2	60	10	10	2
3	10	80	50	0
4	40	30	30	8
5	60	10	70	2
6	20	70	50	4

예를 들어, 식재료 1, 3, 5를 선택하면 영양분은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이 된다. 대신 2, 3, 4를 선택하면 영양분의 합은 110, 130, 90, 10, 비용은 180이 되므로, 앞의 방법보다는 더 나은 선택이 된다.

입력으로 식재료 표가 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

---

입력

첫 줄에 식재료의 개수
$N$이 주어진다.

다음 줄에는 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 나타내는 정수
$mp$,
$mf$,
$ms$,
$mv$가 주어진다.

이어지는
$N$개의 각 줄에는
$i$번째 식재료의 단백질, 지방, 탄수화물, 비타민과 가격이 5개의 정수
$p_i$,
$f_i$,
$s_i$,
$v_i$,
$c_i$와 같이 주어진다. 식재료의 번호는 1부터 시작한다.

---

출력

첫 번째 줄에 최소 비용을 출력하고, 두 번째 줄에 조건을 만족하는 최소 비용 식재료의 번호를 공백으로 구분해 오름차순으로 한 줄에 출력한다. 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.

조건을 만족하는 답이 없다면 -1을 출력하고, 둘째 줄에 아무것도 출력하지 않는다.

---

풀이

접근방법

시간제한 2초, 메모리 512MB이다.

단순 구현문제이다.

전체를 탐색하면서 포함한 경우, 제외한 경우를 모두 확인하며 조건을 검사한다.

처음에는 별도의 정렬없이 한 번에 해결하고자 하였으나, 아이디어가 잘 생각나지 않아 모두 다 기록하고 정렬을 통해서 가장 작은 조합을 찾았다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
	static class Food {
		int mp;
		int mf;
		int ms;
		int mv;
		int price;

		Food(int a, int b, int c, int d, int e) {
			mp = a;
			mf = b;
			ms = c;
			mv = d;
			price = e;
		}

		Food(String[] splitedLine) {
			mp = stoi(splitedLine[0]);
			mf = stoi(splitedLine[1]);
			ms = stoi(splitedLine[2]);
			mv = stoi(splitedLine[3]);
			price = stoi(splitedLine[4]);
		}

		public void add(Food other) {
			mp += other.mp;
			mf += other.mf;
			ms += other.ms;
			mv += other.mv;
			price += other.price;
		}

		public Food minus(Food other) {
			return new Food(this.mp - other.mp, this.mf - other.mf, this.ms - other.ms, this.mv - other.mv,
				this.price - other.price);
		}
	}

	static Food[] foods;

	static int N, minValue;
	static Food target;
	static Set<Integer> set;
	static List<String> list;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = stoi(in.readLine());
		set = new HashSet<>();
		list = new ArrayList<>();
		String[] splitedLine = in.readLine().split(" ");
		target = new Food(stoi(splitedLine[0]), stoi(splitedLine[1]), stoi(splitedLine[2]), stoi(splitedLine[3]), 0);

		foods = new Food[N + 1];
		Food sum = new Food(0, 0, 0, 0, 0);
		minValue = Integer.MAX_VALUE;
		for (int i = 1; i <= N; ++i) {
			foods[i] = new Food(in.readLine().split(" "));
			sum.add(foods[i]);
			set.add(i);
		}

		// 시뮬레이션을 해보자.
		simulation(sum, 1);

		// 만족시키는 조합이 있었다면
		if (list.size() > 0) {
			System.out.println(minValue); // 가격
			Collections.sort(list); // 정렬을 통한 조합 확인
			String s = list.get(0);
			for (int i = 0; i < s.length(); i++) {
				System.out.print(s.charAt(i));
			}
		} else
			System.out.println(-1);
	}

	private static void simulation(Food sum, int depth) {
		if (depth > N) {
			if (check(sum, target)) {
				if (sum.price <= minValue) {
					if (minValue > sum.price) 
						list.clear(); // 기존 보다 저렴한 가격이다. 기존의 조합을 전부 버리자.
					String str = "";
                    // 조건을 만족하므로, 조합을 기록해두자.
					for (int i : set) {
						str += Integer.toString(i);
						str += " ";
					}
					list.add(str);
					minValue = sum.price;
				}
			}
			return;
		}

		// i번째 food를 제외시켜 본다.
		set.remove(depth);
		simulation(sum.minus(foods[depth]), depth + 1);
		set.add(depth);

		// i번째 food를 제외하지 않는다.
		simulation(sum, depth + 1);
	}

	private static boolean check(Food sum, Food target) {
		if (sum.mp >= target.mp && sum.mf >= target.mf && sum.ms >= target.ms && sum.mv >= target.mv)
			return true;
		return false;
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}