BOJ 2994 - 내한 공연

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	183	66	55	42.308%

문제

---

"The Drinking Musicians"는 2034년 그래미 어워즈에서 총 6관왕에 오른 유명한 N인조 밴드이다. 이 밴드의 음악은 엄청난 힘을 가지고 있어서, 사람의 생각을 조절할 수 있다. 대표적인 예로 결혼식에서 이 밴드의 "그 남자가 저기 있어"를 축가로 부르면, 모든 신부가 그 남자를 찾아 결혼식장을 나선다고 한다.

이 밴드의 공연을 보는 것은 쉽지 않다. 밴드는 정시에 도착하지 않으며, 공연장의 위치도 잘 모른다. 또, 공연장에 도착했더라도 길을 자주 잃어서 공연장을 찾지 못한다.

무대에 올라서 공연을 시작했다고 문제가 끝나는 것은 아니다. 각 멤버는 공연 도중에 자주 휴식을 취하러 백스테이지로 사라진다. 하지만 멤버 셋 이상이 동시에 휴식을 취하면, 무대 위의 남아있는 멤버들은 모두 큰 혼란에 빠지게 되고 연주를 더 이상 진행할 수 없다.

콘서트는 총 T분이고, 콘서트 도중에 각 멤버는 적절히 휴식을 가질 것이다. 각 멤버가 가지는 휴식 시간은 미리 알고있다.

이 밴드의 내한공연을 30년만에 성사시킨 상근이는 공연을 성공적으로 마치기 위해서 멤버들이 휴식을 가지는 시간을 계획하려고 한다. 무대 위에서 휴식을 취하러 가는 멤버는 많아야 두 명 이어야 한다. 또, 모든 휴식은 콘서트 도중에 일어나야 한다.

모든 멤버는 단 한 번의 휴식을 가질 수 있다. 각 멤버들이 공연이 시작하고 몇 분이 지나면 휴식을 취하러 가도 되는지 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 콘서트의 길이 T와 멤버의 수 N이 주어진다. (1 ≤ T ≤ 5000, 1 ≤ N ≤ 500)

다음 줄에는 각 멤버들이 휴식을 취하는 시간이 공백으로 구분되어서 주어진다.

항상 답이 존재하는 경우만 입력으로 주어진다. 하지만, 답이 유일하지 않을 수도 있다.

출력

---

각 멤버가 공연이 시작하고 몇 분이 지난 후에 휴식을 가져야 하는지 출력한다. 입력으로 주어진 순서대로 출력한다.

접근

---

냅색 문제인데, 배낭이 두개라고 생각하면 편하다.
그러면 하나의 배낭에만 최대값으로 채워놓으면 된다.

하지만 각 멤버가 몇 분에 출력해야 되는지 출력해야 된다.
그래서 배낭의 테이블에 이전 노드(담은 물건)을 저장해준다.
그리고, 순회하면서 벌써 true인 값에는 덧씌우지 않는다.

풀이

---

담을 수 있는 T에 제일 가까운 큰 값을 max_time으로 저장했다.
이 후 second에 담아놨던 before 노드를 통해서 isFirst를 체크해준다.
그리고 배낭 두개에 isFirst를 기준으로 순차적으로 휴식을 취하는 시간을 출력해준다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int T, N, arr[500], max_time = 0;
bool isFirst[500];
pair<bool, int> dp[5001]; // 가능, 이전 담은 idx

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	CIN2(T, N);
	FUP(i, 0, N - 1)
	{
		CIN(arr[i]);
		isFirst[i] = false;
	}
	FUP(i, 1, T) dp[i].first = false;
	dp[0] = { true, -1 };
	FUP(i, 0, N - 1)
	{
		FDOWN(j, max_time, 0)
		{
			if (dp[j].first && j + arr[i] <= T && !dp[j + arr[i]].first)
			{
				dp[j + arr[i]] = { true, i };
				max_time = max(max_time, j + arr[i]);
			}
		}
	}
	int idx = max_time;
	while (idx != 0)
	{
		int node = dp[idx].second;
		isFirst[node] = true;
		idx -= arr[node];
	}
	int bag[2] = { 0, 0 };
	FUP(i, 0, N - 1)
	{
		COUT2(bag[isFirst[i]], "");
		bag[isFirst[i]] += arr[i];
	}

	return 0;
}