취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2994번 문제인 내한 공연이다.
문제는 아래 링크를 확인하자.

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

각 멤버의 쉬는 시간을 구성하는 것을 다르게 모델링하면 주어지는 각 공연시간과 길이의 막대기들을 모두 사용해 길이가 각각 T 이하인 두 개의 긴 막대기를 만드는 문제로 생각할 수 있다. 두 문제가 동치임은 어렵지 않게 관찰 가능하므로 설명을 생략한다.

위의 막대기 문제는 T 이하의 길이 중 주어진 막대기들의 일부를 이용해 구성할 수 있는 가장 긴 길이를 찾는 것으로 해결할 수 있다. 답의 존재성이 보장되어있으므로 남은 막대기들의 길이의 합 또한 자연스럽게 T 이하가 될 것이다. 이와 같은 길이는 knapsack dp를 이용해 간단히 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int T, N;
int resting[501];
int dp[5001];

int idx;
int visited[5001];
int psum1, psum2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T >> N;
	for (int i = 1; i <= N; i++) cin >> resting[i];
	
	dp[0] = -1;
	for (int i = 1; i <= N; i++) {
		int r = resting[i];
		for (int t = T; t >= r; t--) {
			if (!dp[t] && dp[t - r]) dp[t] = i;
		}
	}

	idx = T;
	while (!dp[idx]) idx--;
	while (dp[idx] > -1) {
		visited[dp[idx]] = 1;
		idx -= resting[dp[idx]];
	}

	for (int i = 1; i <= N; i++) {
		if (visited[i]) {
			cout << psum1 << ' ';
			psum1 += resting[i];
		}
		else {
			cout << psum2 << ' ';
			psum2 += resting[i];
		}
	}
}