BOJ 백준 2994 내한 공연

 

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

 

[ 문제 요약 ]

• 공연의 전체 시간 T(최대 5,000분)와 멤버의 수(최대 500)이 주어집니다.
• 각 멤버는 공연 시간 내에서 정해진 길이의 휴식 시간이 필요합니다. 단, 공연 중 동시에 최대 2명까지만 휴식을 갈 수 있습니다.
• 답이 항상 있는 경우만 주어집니다.
• 각 멤버의 순서대로 언제 휴식을 갈지 휴식 가는 시간을 멤버마다 출력하면 됩니다. 답은 여러 개일 수 있으므로 그중 하나만 출력하면 됩니다.

 

[ 테스트 케이스 설명 ]

8 3		// 총시간(1<=5,000), 멤버수(1<=500)
4 4 4		// 각 멤버들이 휴식을 취하는 시간, 휴식은 동시에 최대 2명까지만 갈 수 있음
답 : 0 2 4	// 각멤버들이 공연 시작 후 몇 분이 지나면 휴식을 취하러 가도 되는지 구하라

 

[ 문제 풀이 ]

 

배낭 2개에 각 멤버를 채우는 방식으로 해결할 수 있습니다.

 

먼저 하나의 배낭에 멤버들의 휴식 시간을 최대한으로 집어넣습니다.

 

그렇게 되면 선택되지 않은 나머지 멤버들은 다른 배낭에 아무렇게나 넣어도 정답이 됩니다.

 

답이 무조건 존재한다고 하였으니, 배낭 1개에 휴식 시간을 최대한 채우면 다른 배낭에 선택되지 않은 남은 멤버들로 무조건 답을 구할 수 있는 겁니다.

 

멤버는 한 번만 선택이 가능하니 0/1 배낭 문제로 볼 수 있습니다.

 

여기서 중요한 것은 배낭을 최대한 채울 때, 선택한 멤버들에 대해서 어떻게 시작 시간을 구할 수 있느냐?입니다.

 

답은 간단합니다.

 

dp 배열을 구할 때, 최대 휴식 시간이 갱신될 때마다 그 시점의 시간에 선택된 멤버를 입력해 주기만 하면 됩니다.

 

시간에 따라 선택된 멤버의 번호를 마킹할 배열 choice를 선언합니다.

for(int j=T; j>=rest[i]; j--)
{
	if(dp[j] < dp[j - rest[i]] + rest[i])
	{
		dp[j] = dp[j - rest[i]] + rest[i];
		choice[j] = i; // 이 부분이 시간에 따라 선택되는 멤버의 인덱스(i)를 저장함
	}
}

 

위 코드를 보면 dp 값의 갱신은 일반 배낭 문제와 똑같고, 갱신될 때마다 현재 시간(j)에 따른 선택된 멤버의 인덱스(i)를 choice 배열에 입력해 주면 됩니다.

 

그리고 choice 배열을 역으로 추적해 선택된 멤버의 시작 시간을 구할 수 있습니다.

 

그 시작 시간을 최종 결과를 담을 result라는 배열에 입력해 줍니다.

 

choice 배열을 활용해 역 추적하는 부분이 이해가 안 간다면 디버깅을 해봐야 이해가 될 겁니다.

 

그러면 일단 배낭 한 개에 대해 멤버는 최대한 채웠으므로 나머지는 선택되지 않은 멤버의 값만

 

입력해 주면 됩니다.

 

dp 배열 한 개에 휴게 시간을 최대한 가득 차게 분배하려면 어떻게 dp를 만들어야 하나 고민할 수 있는데,

 

이 부분은 아주 간단합니다.

 

일반 배낭 문제에서 가치와 무게가 있는데, 여기서 가치와 무게 모두 멤버의 쉬는 시간으로 두면 됩니다.

 

이렇게 되면, 어떤 j 분의 용량을 채울 수 있다면, 그 dp[j] 안에 있는 값은 j가 되는 것입니다.

 

예를 들어 총 공연 시간이 10이고, 멤버의 휴식 시간이 1 2 3 4 5일 때, dp를 돌린 후 dp 배열에는 아래와 같은 값이 들어가 있게 됩니다.

 

dp = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T		= Integer.parseInt(st.nextToken());	// 총시간(1<=5,000)
		int N		= Integer.parseInt(st.nextToken());	// 멤버수(1<=500)
		int rest[]	= new int[N + 1];					// 멤버들 휴식 시간
		int choice[]= new int[T + 1];
		int dp[]	= new int[T + 1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
		{
			rest[i] = Integer.parseInt(st.nextToken());
			// 하나의 배낭에 휴식 시간을 빈틈 없이 가득 채울 수 있도록 꽉 채운다.
			// 이 때, 선택한 멤버의 번호도 입력해 놓는다.
			for(int j=T; j>=rest[i]; j--)
			{
				if(dp[j] < dp[j - rest[i]] + rest[i])
				{
					dp[j] = dp[j - rest[i]] + rest[i];
					choice[j] = i;
				}
			}
		}
		int result[]= new int[N + 1];
		int time = T;
		// 시간에 따른 선택된 멤버가 choice에 기록되어있으니, 이를 통해 역순으로 순회하며
		// 해당 멤버가 들어간 시간을 result에 입력한다.
		while(time > 0)
		{
			int idx = choice[time];	// 해당 시간에 선택된 
			
			result[idx] = time - rest[idx] + 1;
			time -= rest[idx];
		}
		////// 이 이하부터는, 나머지 선택되지 않은 멤버에 대해 채우는 것
		time = 1;
		// result에 값이 0인 것은 아직 선택되지 않은 멤버이므로 값이 0인 것들에 대해 
		// 순차적으로 순회하며, 그 멤버의 진입 시간을 넣는다. 이 진입시간을 위해 time을 별도로 선언했다. 
		for(int i=1; i<=N; i++)
		{
			if(result[i] == 0)
			{
				result[i] = time;	// 선택되지 않은 멤버의 진입시간 세팅
				time += rest[i];	// 진입시간을 이제 선택된 멤버의 시간과 더해서 다음 진입시간을 만듬
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=1; i<=N; i++)
			// 출력시에, 시간은 0 부터 시작이므로 -1을 하여 보정처리 한다.
			sb.append(result[i] - 1).append(' ');
		
		System.out.print(sb);
	}
}