문제

문제 링크

해설

• 주어진 최대 15가지의 식재료 중 조건을 만족하는 최소 가격 조합을 찾아야 하므로 모든 경우의 수를 탐색해야 합니다. 따라서 모든 경우의 수는 2¹⁵로 시간제한 내로 풀 수 있습니다.
• 특히 '15가지'라는 점에 주목합시다. 32 이하의 수일 때 한 번쯤 '비트플래그'를 사용할 수 있는지 의심해볼 수 있습니다.
  • 모든 경우의 수를 탐색해야 하므로 쉬프트 연산 1 << 15 를 이용할 수 있습니다.
  • n번째 bit가 '1'일 때 n번째 식재료를 선택하는 경우의 수로 가정할 수 있습니다.
• 어떤 경우의 수에서, 문제의 조건을 만족했을 때, 가격을 합산한 뒤 최솟값을 갱신할 수 있다면 갱신합니다.
  • 이때, 최솟값을 갱신할 수는 없지만, 출력 순서는 갱신할 수 있다면,
  • 현재 활성화된 k번째 bit들을 문자열로 바꿔 출력하면 됩니다.

코드

#include <iostream>
using namespace std;

struct ingredients { int p, f, s, v, c; };

int N, mp, mf, ms, mv;
ingredients foods[15];

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N >> mp >> mf >> ms >> mv;
	for (int i = 0; i < N; i++)
		cin >> foods[i].p >> foods[i].f >> foods[i].s >> foods[i].v >> foods[i].c;
	
	int answer = 1e9, answer_bit = 0;
    // N개의 음식에 대한 모든 경우의 수 = 2^N
	for (int i = 0; i < (1 << N); i++) {
		int p = 0, f = 0, s = 0, v = 0, c = 0;
        // set된 bit번째 재료가 선택됐다고 가정
		for (int j = 0; j < 15; j++) {
			if (i & (1 << j)) {
				p += foods[j].p;
				f += foods[j].f;
				s += foods[j].s;
				v += foods[j].v;
				c += foods[j].c;
			}
		}
		if (p >= mp && f >= mf && s >= ms && v >= mv) {
			if (c < answer) {
				answer = c;
				answer_bit = i;
			}
            // 같은 경우 사전순으로 출력해야하기 때문에 문자열로 변경 후 비교
			else if (c == answer) {
				answer = c;
				string lhs = "", rhs = "";
				for (int j = 0; j < 16; j++) {
					if (i & (1 << j)) lhs.push_back((char)(j + 1));
					if (answer_bit & (1 << j)) rhs.push_back(char(j + 1));
				}
				if (lhs < rhs) answer_bit = i;
			}
		}
	}
	if (answer == 1e9) { 
		cout << -1 << '\n';
	}
	else {
		cout << answer << '\n';
		for (int i = 0; i < 16; i++)
			if (answer_bit & (1 << i)) cout << (i + 1) << ' ';
		cout << '\n';
	}
	return 0;
}

소스코드 링크

결과

• 같은 가격일 때, 사전순으로 빠른 것을 출력하는 점에서 어려움을 겪었습니다.