BOJ 백준 10982 행운쿠키 제작소

kyjdummy 2025. 4. 10. 21:04

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

[ 문제 요약 ]

두 오븐에 반죽들을 적절히 배분할 때, 두 오븐에서 동시에 작업한다고 가정했을 때, 전체 완료 시간(두 오븐의 작업 시간 중 큰 값)을 최소로 만드는 배분을 찾는 것

[ 테스트 케이스 설명 ]

2	// 테스트케이스 수
3	// 반죽의개수(1<=1000)
10 5	// 오븐 1,2에서 각각 구워지는 걸리는 시간(1<=100)
8 5
8 5
4
15 20
30 21
5 3
10 10
// 테스트 케이스마다 최소시간 출력
10
25

[ 문제 풀이 ]

반죽들을 두 오븐에 어떻게 분배하면, 두 오븐 중 작업 시간이 더 긴 쪽이 최소가 될까를 생각해야 합니다.

이를 생각하기 위해 문제 조건을 먼저 정리합니다.

[문제 조건 정리]

각 반죽은 오븐 1에서 굽거나 오븐 2에서 굽는 둘 중 하나의 선택지가 있다.
만약 어떤 반죽을 오븐 1에 배정하면, 그 반죽은 시간 a를 소요하고, 반대로 오븐 2에 배정하면 시간 b가 소요된다. 두 오븐의 처리 시간이 서로 상호 배타적이다.
전체 작업이 끝나는 시간은 두 오븐이 동시에 작동할 때 두 오븐의 처리 시간 중 더 큰 값이 된다.

“어떤 반죽들을 오븐 1에 배정했을 때, 오븐 1의 총 소요시간은 얼마고, 동시에 그 반죽들로 인해 오븐 2에는 어떤 시간이 발생하는지를 계산할 수 있을까?”

라는 질문을 그대로 코드로 구현할 수 있습니다.

두 오븐 처리 시간이 상호 배타적이기 때문에 전체 반죽에 대해, 오븐 1에 특정 반죽들을 배정한다면,

여러 배정에 따른 오븐 1의 총 시간은 여러 가지가 될 수 있고, 그리고 동시에 이런 배정들은 오븐 2에서는 얼마만큼의

시간을 절약하거나 추가로 필요한지를 결정하게 됩니다.

DP 배열의 인덱스를 [오븐 1의 사용 시간]으로 두고,

DP[X]는 [오븐 1에 X 분을 배정했을 때 오븐 2가 처리해야 하는 시간의 최솟값]으로 정의하면 이 문제를 풀 수 있습니다.

예를 들어

[오븐 1이 10분 걸려서 처리할 것을, 오븐 2에 배정하면 5분만 걸린다]

를 알 수 있게 오븐 1의 시간을 기준으로 오븐 2의 시간을 구합니다.

두 그룹으로 나누는 문제를 → 부분 집합 선택 문제로 모델링 하여 풉니다.

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Node{
	int a, b;
	Node(int a, int b){
		this.a=a;
		this.b=b;
	}
}
class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T-->0)
		{
			int N		= Integer.parseInt(br.readLine());	//반죽의개수(1<=1,000)
			Node node[] = new Node[N];
			int sumA	= 0;
			
			for(int i=0; i<N; i++)
			{
				StringTokenizer st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());// 오븐 1에서 구워지는 걸리는 시간(1<=100)
				int b = Integer.parseInt(st.nextToken());// 오븐 2에서 구워지는 걸리는 시간(1<=100)
				node[i] = new Node(a,b);
				sumA += a;
			}

			// dp의 인덱스의 의미 : 오븐 1에서 구울 때의 시간의 합
			// dp[x]안에 담긴 값의 의미 : x시간 동안 오븐 2에서 구울 때의 시간의 합 중 최소
			int dp[] = new int[sumA + 1];
			
			Arrays.fill(dp, 1<<30);
			
			dp[0] = 0;
			
			for(Node now : node)
			{
				// 오븐 1에서 구워지는 총시간을 역순으로 내려가면서 탐색
				for(int j=sumA; j>=now.a; j--)
				{
					// dp[j]안에는 j시간동안 오븐 2에서 구울 때의 시간의 합 중 최소 값이 들어가야 한다.
					dp[j] = Math.min(dp[j], dp[j-now.a] + now.b);
				}
			}
			int ans = 1<<30;
			
			for(int j=0; j<=sumA; j++)
				// 오븐 1의 시간의 총합이 j일 때, 오븐 2의 시간의 총합은 sumA - j 인덱스 안에 담긴 값이다.
				ans = Math.min(ans, Math.max(j, dp[sumA - j]));
			
			sb.append(ans).append('\n');
		}
		System.out.print(sb);
	}
}