[PAST 알고리즘 시리즈] Part 1 보충 — おまかせ 문제 풀이

목차

Step	주제	핵심 질문
0	문제 이해하기	무엇을 구하는 문제인가?
1	완전 탐색의 한계	직접 풀면 왜 시간 초과인가?
2	판정 문제로 변환하기	어떤 질문으로 바꿀 수 있는가?
3	수식 변형 — 핵심 관찰	판정 함수를 어떻게 효율화하는가?
4	판정 함수 check(X) 구현	코드로 옮기면?
5	이분 탐색으로 최적값 찾기	전체를 어떻게 조합하는가?
6	계산량 분석 & 정리	시간 안에 통과하는가?

Step 0 — 문제 이해하기

문제 요약

소셜 게임에서 몬스터를 합성합니다:

• 소유 몬스터 N마리: 각각 질량 $A_i$, 마력 $B_i$
• 도우미 몬스터 M마리: 각각 질량 $C_i$, 마력 $D_i$
• $N + M$ 마리 중 정확히 5마리를 선택하여 합성 (도우미 몬스터는 최대 1마리)
• 합성 강도 = (선택한 5마리의 마력 합) ÷ (선택한 5마리의 질량 합)
• 강도의 최대값을 출력하라

제약 조건

• $5 \leq N \leq 1000$
• $1 \leq M \leq 100$
• $1 \leq A_i, B_i \leq 100000$
• $1 \leq C_i, D_i \leq 100000$
• 모든 값은 정수

입출력 예시

입력:

6 2
10 30
20 60
10 10
30 100
50 140
40 120
10 3
30 1

출력:

3.0000000000000

1, 2, 4, 5, 6번째 소유 몬스터를 선택하면, $마력 합 = 30 + 60 + 100 + 140 + 120 = 450$, $질량 합 = 10 + 20 + 30 + 50 + 40 = 150$이므로 $강도 = 450 / 150 = 3.0$입니다.

Step 1 — 완전 탐색의 한계

가장 단순한 접근: 가능한 모든 5마리 조합을 시도하고, 각 조합의 강도를 계산하여 최댓값을 구합니다.

조합 수 계산

도우미 몬스터를 사용하지 않는 경우:

$\binom{N}{5} = \binom{1000}{5} \approx 8.3 \times 10^{12}$

도우미 몬스터를 1마리 사용하는 경우:

$\binom{N}{4} \times M \approx 4.1 \times 10^{12}$

총 조합 수가 약 $10^{13}$ 으로, 실행 시간 제한(5초) 내에 처리하는 것은 불가능합니다.

Step 2 — 판정 문제로 변환하기

직접 최대값을 구하기 어려우니, 질문의 형태를 바꿔봅시다.

핵심 아이디어

원래 문제:

이를 다음과 같은 판정 문제(Yes/No 질문)로 바꿉니다:

이 판정 문제를 빠르게 풀 수 있다면, $X$의 값을 조절하여 최적의 $X$(= 강도 최대값)를 찾을 수 있습니다.

단조성 확인

이 판정 문제의 답은 $X$의 값에 대해 단조적입니다:

X = 0        → ✅ (어떤 조합이든 강도 ≥ 0)
X = 1        → ✅ 
X = 2        → ✅ 
X = 3        → ✅  ← 여기가 최대값!
X = 3.0001   → ❌ 
X = 4        → ❌
X = 100000   → ❌

가능한 구간(✅)와 불가능한 구간(❌)의 경계가 정확히 하나만 존재 → 이분 탐색으로 경계를 찾을 수 있음!

Step 3 — 수식 변형 (핵심 관찰)

판정 문제를 빠르게 풀려면, "강도 ≥ X"라는 조건을 다루기 쉬운 형태로 변형해야 합니다.

변형 과정

5마리를 선택했다고 합시다 ($a, b, c, d, e$번째 몬스터). 강도가 $X$ 이상이 되려면:

$\frac{(B_a + B_b + B_c + B_d + B_e)}{(A_a + A_b + A_c + A_d + A_e)} \geq X$

양변에 분모(질량 합, 항상 양수)를 곱합니다:

$B_a + B_b + B_c + B_d + B_e \geq X \cdot (A_a + A_b + A_c + A_d + A_e)$

우변을 좌변으로 옮깁니다:

$(B_a - A_a X) + (B_b - A_b X) + (B_c - A_c X) + (B_d - A_d X) + (B_e - A_e X) \geq 0$

핵심 정의

각 몬스터 $i$에 대해 새로운 값 $P_i$를 정의합니다:

$P_i = B_i - A_i \cdot X$

그러면 판정 문제는:

$X$는 이분 탐색에서 고정된 값이므로, $P_i$는 단순한 뺄셈과 곱셈으로 계산됩니다. 정렬 후 상위 5개의 합만 확인하면 됩니다.

Step 4 — 판정 함수 check(X) 구현

Step 3의 아이디어를 코드로 옮깁니다. 두 가지 케이스를 모두 확인해야 합니다:

케이스 분리

1. 도우미 몬스터 미사용: 소유 몬스터 5마리만 선택
2. 도우미 몬스터 1마리 사용: 소유 몬스터 4마리 + 도우미 몬스터 1마리

도우미 몬스터에 대해서도 같은 변형을 적용합니다: $Q_j = D_j - C_j \cdot X$

Java 코드 예시 - check 함수

// N, M, A[], B[], C[], D[] 는 클래스 필드로 선언되어 있다고 가정

static boolean check(double X) {
    // ── 1단계: 소유 몬스터의 P 값 계산 ──
    double[] P = new double[N];
    for (int i = 0; i < N; i++) {
        P[i] = B[i] - A[i] * X;
    }

    // ── 2단계: P를 오름차순 정렬 (큰 값이 뒤에) ──
    Arrays.sort(P);

    // ── 3단계: 케이스 1 — 도우미 미사용 ──
    //    P의 상위 5개(배열 끝에서 5개)의 합
    double sum5 = 0;
    for (int i = N - 1; i >= Math.max(0, N - 5); i--) {
        sum5 += P[i];
    }
    if (sum5 >= -1e-9) return true;  // 부동소수점 오차 고려

    // ── 4단계: 케이스 2 — 도우미 1마리 사용 ──
    //    P의 상위 4개 + Q의 최대값
    double sum4 = 0;
    for (int i = N - 1; i >= Math.max(0, N - 4); i--) {
        sum4 += P[i];
    }

    double maxQ = Double.NEGATIVE_INFINITY;
    for (int j = 0; j < M; j++) {
        maxQ = Math.max(maxQ, D[j] - C[j] * X);
    }

    return sum4 + maxQ >= -1e-9;  // 부동소수점 오차 고려
}

각 단계의 의미

단계	코드	의미
1단계	P[i] = B[i] - A[i] * X	각 소유 몬스터의 "가치"를 현재 X 기준으로 계산
2단계	Arrays.sort(P)	정렬하여 상위 k개를 쉽게 뽑을 수 있게 준비
3단계	상위 5개 합 ≥ 0?	도우미 몬스터 없이 강도 X 이상 가능한지 확인
4단계	상위 4개 + max(Q) ≥ 0?	도우미 몬스터 1마리로 더 나은 조합이 있는지 확인

Step 5 — 이분 탐색으로 최적값 찾기

판정 함수 check(X)가 완성되었으므로, 이제 이분 탐색으로 경계(= 강도 최대값)를 찾습니다.

탐색 범위 설정

• 하한 (lo): 0 — 강도는 항상 0 이상 (마력, 질량 모두 양수
• 상한 (hi): $10^9$ — 제약 조건상 $B_i \leq 100000, A_i \geq 1$이므로 강도는 100000을 넘지 않음. 넉넉하게 $10^9$로 설정

실수 이분 탐색의 특징

정수 이분 탐색에서는 while (hi - lo > 1) 같은 종료 조건을 사용하지만, 실수 이분 탐색에서는 반복 횟수를 고정하는 것이 안전합니다.

완성 코드 예시

import java.util.*;

public class Main {
    static int N, M;
    static long[] A, B, C, D;

    public static void main(String[] args) {
        // ── 입력 ──
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        A = new long[N]; B = new long[N];
        C = new long[M]; D = new long[M];

        for (int i = 0; i < N; i++) {
            A[i] = sc.nextLong();
            B[i] = sc.nextLong();
        }
        for (int i = 0; i < M; i++) {
            C[i] = sc.nextLong();
            D[i] = sc.nextLong();
        }

        // ── 이분 탐색 ──
        double lo = 0, hi = 1e9;
        for (int iter = 0; iter < 100; iter++) {
            double mid = (lo + hi) / 2.0;
            if (check(mid)) {
                lo = mid;   // mid 이상 가능 → 더 큰 값 탐색
            } else {
                hi = mid;   // mid 이상 불가능 → 더 작은 값 탐색
            }
        }

        // ── 출력 ──
        System.out.printf("%.13f%n", lo);
    }

    static boolean check(double X) {
        // 소유 몬스터의 P 값 계산
        double[] P = new double[N];
        for (int i = 0; i < N; i++) {
            P[i] = B[i] - A[i] * X;
        }
        Arrays.sort(P);

        // 케이스 1: 소유 몬스터 5마리
        double sum5 = 0;
        for (int i = N - 1; i >= Math.max(0, N - 5); i--) {
            sum5 += P[i];
        }
        if (sum5 >= -1e-9) return true;

        // 케이스 2: 소유 몬스터 4마리 + 도우미 1마리
        double sum4 = 0;
        for (int i = N - 1; i >= Math.max(0, N - 4); i--) {
            sum4 += P[i];
        }
        double maxQ = Double.NEGATIVE_INFINITY;
        for (int j = 0; j < M; j++) {
            maxQ = Math.max(maxQ, D[j] - C[j] * X);
        }
        return sum4 + maxQ >= -1e-9;
    }
}

이분 탐색 동작 과정 (예제 기준)

iter 0:  lo=0,  hi=1e9,  mid=5e8      → check(5e8)=false   → hi=5e8
iter 1:  lo=0,  hi=5e8,  mid=2.5e8    → check(2.5e8)=false → hi=2.5e8
...
(범위가 급격히 줄어듦)
...
iter 50: lo≈3.0, hi≈3.0+ε             → 충분히 수렴
...
iter 99: lo≈3.0000000000000           → 최종 답

Step 6 — 계산량 분석 & 정리

시간 복잡도

부분	계산량
check(X) 1회	$O(N \log N)$ — P 계산 $O(N)$ + 정렬 $O(N \log N)$ + Q 탐색 $O(M)$
이분 탐색 반복	$O(\log(\max{A}))$ 회 (실수 이분 탐색의 경우 상수 100회)
전체	$O(N \log N \cdot \log(\max{A}))$

$N = 1000$일 때: $1000 \times 10 \times 100 = 10^6$ 정도의 연산으로, 시간 제한 내에 여유 있게 통과합니다.

이 문제에서 배운 패턴

핵심 요약

항목	내용
문제 유형	분수식의 최대화 (마력 합 / 질량 합)
접근법	최적화 → 판정 문제 변환 + 이분 탐색
핵심 수식	$P_i = B_i - A_i X$ 로 변환 후, 상위 5개(또는 4+1)의 합 ≥ 0 판정
이분 탐색 타입	실수 이분 탐색 (반복 100회 고정)
계산량	$0(N \log N \cdot \log(\max{A}))$

관련 링크

• Part 1 본문: 이분 탐색 심화 — 이 문제를 포함한 3가지 이분 탐색 기법의 전체 정리
• 문제 URL: [第一回 アルゴリズム実技検定 過去問] — M - おまかせ
• 소스코드: tsutaj/pastbook-2-source-code (Github)