선물 배분 문제 정리

JunHyeok Seo·2025년 3월 12일

선불배분 완전탐색

algorithm

목록 보기

8/30

선물 배분 문제 정리

문제 개요

N명의 학생에게 B만큼의 예산으로 선물을 구매.
학생마다 가격 P(i)와 배송비 S(i)가 있음.
선생님은 선물 하나를 반값으로 살 수 있는 쿠폰을 가짐.
최대한 많은 학생에게 선물을 주는 것이 목표.

해결 방법

(P + S) 값이 작은 순서로 정렬 → 비용이 적은 선물을 먼저 구매.
(P + S) 값이 동일하면 P가 작은 순서로 정렬 → 쿠폰을 더 비싼 선물에 효과적으로 사용.
모든 선물에 대해 쿠폰을 한 번씩 적용해보며 최적의 결과 탐색.

정렬이 필요한 이유

예산을 최대한 활용하려면 비용이 적은 선물부터 구매해야 함.
비싼 선물을 먼저 구매하면 예산이 부족하여 더 적은 학생에게 선물을 줄 가능성이 높음.
정렬을 하면 최소 비용으로 최대한 많은 학생에게 선물을 줄 수 있음.

동일한 값이 있을 때 P가 작은 순으로 정렬하는 이유

쿠폰을 사용할 선물을 전략적으로 선택해야 함.
P가 큰 항목이 앞에 오면 쿠폰을 비효율적으로 사용할 가능성이 있음.
P가 작은 항목을 먼저 배치하면 쿠폰을 더 비싼 선물에 활용할 기회를 남길 수 있음.

정렬 기준

Arrays.sort(items, (a, b) -> {
    int costA = a.price + a.shipping;
    int costB = b.price + b.shipping;
    
    if (costA == costB) {
        return Integer.compare(a.price, b.price);  // P(i) 작은 순 정렬
    }
    return Integer.compare(costA, costB);  // P(i) + S(i) 기준 정렬
});

코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int b = sc.nextInt();
		int[][] p = new int[n][2];
		for(int i = 0; i < n; i++){
			p[i][0] = sc.nextInt();
			p[i][1] = sc.nextInt();
		}

		int[][] sortedArr = Arrays
				    .stream(p)
				    .sorted(
						    Comparator
								    .comparingInt((int[] row) -> Arrays.stream(row).sum())
								    .thenComparing((int[] row) -> row[0])
				    )
				    .toArray(int[][]::new);

		int maxCnt = 0;
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			int tmpB = b;
			for (int j = 0; j < n; j++) {
				int price = sortedArr[j][0];
				int delivery = sortedArr[j][1];

				if (i == j)
					price /= 2;

				if (tmpB - (price + delivery) >= 0) {
					tmpB -= (price + delivery);
					cnt++;
				}
			}

			maxCnt = Math.max(maxCnt, cnt);
		}

		System.out.println(maxCnt);
	}
}