BOJ 백준 5909 Bale Share

 

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

 

[ 문제 요약 ]

• 건초더미들과 그 무게들이 주어질 때, 건초더미들을 3개의 그룹으로 나누고, 3개의 건초 더미 중 최댓값이 최소가 되도록 한다.

 

[ 테스트 케이스 설명 ]

 

8	// 건초더미 개수 1<=20
14	// 건초더미 크기 1<=100
2
5
15
8
9
20
4
답 : 26

 

 

[ 문제 해설 ]

 

문제는 세 그룹으로 분할하는 문제지만, 세 그룹을 모두 고려하는 것은 상태가 너무 많아 효율적으로 풀기 어렵습니다.

 

대신, 두 그룹의 합에 대해 동적 계획법(DP)을 적용하여 만들 수 있는 가능한 합들을 기록하고,

 

나머지 세 번째 그룹은 전체 합에서 두 그룹의 합을 빼서 자동으로 결정되는 방식으로 접근합니다.

 

일반 배낭 문제에서는 가치의 최대화를 목표로 하지만,

 

이 문제에서는 세 그룹 중 가증 큰 합(즉, 불균형 정도)을 최소화하는 데 초점을 맞춥니다.

 

문제 해결을 위해 2차원 DP 배열을 사용하여

 

[ 첫 번째 그룹의 합계 i, 두 번째 그룹의 합계 j를 만드는 것이 가능한가? ]

 

를 기록합니다. 나머지 그룹은 전체 합에서 i와 j를 뺀 값(= group3)이 됩니다.

 

dp[i그룹합][j그룹합] = 가능한가?

 

코드를 보면 이해하기 쉽습니다.

 

[ 정답 코드 ]

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N		= Integer.parseInt(br.readLine());	// 건초 더미 개수 1<=20
		int arr[]	= new int[N + 1];
		int sum		= 0;
		
		for(int i=1; i<=N; i++)
			sum += arr[i] = Integer.parseInt(br.readLine());	// 건초 더미 크기 1<=100
		// DP 배열: dp[i][j] = 일부 건초 더미를 그룹1과 그룹2로 나누어, 그룹1의 합이 i, 그룹2의 합이 j가 가능한지 여부
		boolean dp[][] = new boolean[sum + 1][sum + 1];
		
		dp[0][0] = true;// 아무것도 선택하지 않으면 그룹 합은 (0,0)
		// 건초더미 반복
		for(int now : arr)
		{
			for(int i=sum; i>=0; i--)				// 첫 번째 그룹, 중복 선택 방지를 위해 역순 탐색
			{
				for(int j=sum-i; j>=0; j--)			// 두 번째 그룹,	중복 선택 방지를 위해 역순 탐색
				{
					if(i>=now)
						dp[i][j] |= dp[i-now][j];	// i-now , j값이 참이면 i,j도 참임
					
					if(j>=now)
						dp[i][j] |= dp[i][j-now];	// i, j-now값이 참이면 i,j도 참임
				}
			}
		}
		
		int ans = sum + 1;
		
		for(int i=0; i<=sum / 2; i++)	// 그룹 1에 해당하는 값, 건초 그룹 3개중 두번째로 크다.
		{
			for(int j=0; j<=i; j++)		// 그룹 2에 해당하는 값, 건초 그룹 3개중 세번째로 크다.
			{
				int group3 = sum - i - j;// 그룹 3에 해당하는 값, 건초 그룹 3개중 가장 크다.
				// i와 j로 만들 수 있고, 그룹 3이 가장 클 때 결과 갱신
				if(dp[i][j] && group3>=i)
					ans = Math.min(ans, group3);
			}
		}
		
		System.out.print(ans);
	}
}

 

 

[ 코드 해설 ]

• 건초 더미를 순회하며 dp에 값을 갱신하는 부분에서 i와 j 그룹을 역순으로 탐색하는 이유는, 한 건초 더미가 여러 번 사용되는 것을 막기 위함입니다.
• 최종 해 도출 시, i 그룹과 j 그룹을 순회하며 sum에서 i, j 그룹을 빼서 group3을 만듭니다. 그리고 group3이 가능하면서, 그룹 중 가장 클 때(grou3≥ i) 값을 갱신하도록 합니다.

 

이 풀이의 핵심은 동적 계획법(DP)을 활용해 두 그룹의 가능한 합들을 전부 기록한 뒤, 전체 건초의 합에서 두 그룹의 합을 빼 그룹 3의 합을 유도해 내는 것입니다.

 

이 문제를 통해 동적 계획법이 단순한 최대/최소 문제뿐만 아니라, 여러 그룹으로 나눠 균형을 맞추는 다양한 문제에 적용될 수 있음을 이해할 수 있었습니다.