BOJ 백준 31265 훈련

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

 

[ 문제 요약 ]

• N 가지의 훈련 상황이 있고, 각 훈련 상황마다 특정 개수의 훈련이 들어가 있으며, 이 훈련의 각각의 시간이 주어진다. 각 훈련 상황마다 최소 1개 이상의 훈련을 선택해 M 시간을 초과하지 않는, 가장 큰 훈련 시간 총합을 출력합니다.
• 불가할 경우 - 1을 출력합니다.
• 훈련은 중복 선택 불가합니다.
•  

[ 테스트 케이스 설명 ]

5 24			// 훈련상황 가지 수(1<=1,000), 훈련 최대시간(1<=10,000)
5 2 4 1 3		// 각 훈련 상황에 속한 훈련의 개수(1<=1,000)
23 7 11 3 2		// n줄에걸쳐 각 훈련 상황에 속한 훈련의 소요 시간을 나타내는 정수가 주어짐(1<=1,000)
8 10
5 17 20 9
13
1 24 3
// 답 : -1

 

[ 문제 해설 ]

 

훈련 상황마다 반드시 1개 이상 선택하지 않고, 단순히 훈련 중 최대 시간을 구하는 것이라면 일반 배낭문제로 쉽게 구할 수 있습니다.

 

하지만 문제는 훈련 상황마다 반드시 1개 이상 선택해야 합니다.

 

이런 훈련 상황마다 반드시 1개 이상 선택하는 것을 코드에 별도로 넣어 구현해야 할 거 같으나, 2차원 배열로 구현할 때, DP 전이 방식을 수정하면 그 조건은 자연스럽게 지켜지게 됩니다. 스스로 그 조건이 지켜지는 것입니다.

 

보통 2차원 배열로 DP를 구현할 때, 이전 순번에서 썼던 데이터를 현재로 가져오기 위해 이전 데이터를 현재로 복사합니다. 아래 코드와 같이 말입니다.

 

ex) dp[i][j] = dp[i - 1][j]

 

이 의미는 [ 그룹 i를 선택 없이 지나가도 된다 ]는 의미가 됩니다.

 

하지만 이 문제는 그룹당 반드시 하나 이상 골라야 하므로, 이 전이를 빼면 되는 것입니다.

 

이렇게 해서 [항상 그룹당 최소 하나는 선택]이라는 조건이 암묵적으로 보장되게 됩니다.

 

그렇다면 문제는 더 간단해진 것이고, 단순히 boolean 2차원 배열을 선언하여 배낭을 채워주기만 하면 됩니다.

 

아래는 정답 코드와, 그 코드를 좀 더 빠르게 개선한 코드 2개를 보여줍니다.

 

[ 정답 코드 ]

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 N		= Integer.parseInt(st.nextToken());// 훈련상황 가지 수(1<=1,000)
		int M		= Integer.parseInt(st.nextToken());// 훈련 최대시간(1<=10,000)
		int cnt[]	= new int[N + 1];

		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			cnt[i] = Integer.parseInt(st.nextToken());

		// dp[i][j] = i번째 그룹까지 고려했을 때, 합계가 j가 가능한가?
		boolean[][] dp = new boolean[N + 1][M + 1];
		dp[0][0] = true;	// 아무것도 선택하지 않을 때 합 0은 가능

		for(int i=1; i<=N; i++)
		{
			st = new StringTokenizer(br.readLine());
			for(int c=0; c<cnt[i]; c++)
			{
				int t = Integer.parseInt(st.nextToken());
				// 역순으로 순회하여 같은 시간을 중복 선택하지 않도록함
				for(int m=M; m>=t; m--)
				{
                    			// dp[i-1][m-t] → 이전 그룹까지 합(m-t)이 가능했다면, 그룹 i에서 아이템 t를 선택해 m 달성
                    			// dp[i][m-t] → 같은 그룹 i에서 이미 한 번 이상 선택해 합(m-t)이 가능했다면, 그룹 i에서 추가로 아이템 t 선택해 m 달성
                    			// 이 둘만 허용하므로 그룹 i를 완전히 스킵하는 전이(dp[i][m] = dp[i-1][m])가 없어,
                   			// 항상 그룹당 최소 1개는 선택이 보장된다.
					if(dp[i-1][m-t] || dp[i][m-t])
						dp[i][m] = true;
				}
			}
		}
		// dp[N]그룹에 최종적으로 true가 있는 것이 답이되므로 가장큰 M부터 탐색
		for(int i=M; i>=0; i--)
		{
			if(dp[N][i])
			{
				System.out.print(i);
				return;
			}
		}

		System.out.print(-1);
	}
}

 

[ 속도 개선 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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 N		= Integer.parseInt(st.nextToken());// 훈련상황 가지 수(1<=1,000)
		int M		= Integer.parseInt(st.nextToken());// 훈련 최대시간(1<=10,000)
		int cnt[]	= new int[N + 1];

		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			cnt[i] = Integer.parseInt(st.nextToken());

        	// dp[j] = 합이 j인 상태가 마지막으로 업데이트된 그룹 번호
		// 초기에는 아무 그룹도 사용되지 않았으니 -1
		int dp[] = new int[M + 1];
		
		Arrays.fill(dp, -1);
		
		dp[0] = 0;// 합 0은 그룹 0(가짜 그룹)까지 가능
		
		for(int i=1; i<=N; i++)
		{
			st = new StringTokenizer(br.readLine());
			for(int c=0; c<cnt[i]; c++)
			{
				int t = Integer.parseInt(st.nextToken());
				// 역순으로 순회하여 같은 시간을 중복 선택하지 않도록함
				for(int m=M; m>=t; m--)
				{
					// 이전 그룹번호를 prev에 담아옴
					int prev = dp[m - t];
					// (1) prev == i-1: 그룹 i에서 첫 선택
					// (2) prev == i  : 그룹 i에서 이미 한 번 이상 선택한 상태
					if(prev == i - 1 || prev == i)
						dp[m] = i;
				}
			}
		}

		for(int i=M; i>=0; i--)
		{
			if(dp[i] == N)
			{
				System.out.print(i);
				return;
			}
		}

		System.out.print(-1);
	}
}

위 속도 개선 코드는, dp 배열을 1차원으로 선언하고, dp 안에 저장되는 값은 해당 시간의 합까지 구하기 위해 마지막으로 업데이트된 그룹번호를 두었습니다.

 

[ 속도 차이 ]

 

두번째 코드가 180ms로 18% 더 빠릅니다.