[PAST 알고리즘 시리즈] Part 1 보충 — Average and Median 문제 풀이

목차

Step	주제	핵심 질문
0	문제 이해하기	무엇을 구하는 문제인가?
1	완전 탐색의 한계	직접 풀면 왜 시간 초과인가?
2	[평균값] 판정 문제로 변환	평균값 문제를 합계 문제로 바꿀 수 있는가?
3	[평균값] 합계 최대화 DP	선택 조건을 만족하며 합계를 최대화하려면?
4	[평균값] 판정 함수 + 이분 탐색	코드로 옮기면?
5	[중앙값] 판정 문제로 변환	중앙값 문제를 합계 문제로 바꿀 수 있는가?
6	[중앙값] 동일 DP 재활용	평균값과 무엇이 같고 무엇이 다른가?
7	완성 코드 예시	전체를 어떻게 조합하는가?
8	계산량 분석 & 정리	시간 안에 통과하는가?

Step 0 — 문제 이해하기

문제 요약

N장의 카드에서 조건을 만족하도록 카드를 선택합니다:

• N장의 카드: i번째 카드에 정수 $A_i$가 적혀 있음
• 선택 조건: 각 $i$ ($1 \leq i \leq N-1$)에 대해, i번째 카드와 i+1번째 카드 중 적어도 하나는 반드시 선택 (= 2장 연속으로 선택하지 않는 것은 불가)
• 다음 두 값을 각각 구하라:
  1. 선택한 카드에 적힌 정수의 평균값으로서 가능한 최대값
  2. 선택한 카드에 적힌 정수의 중앙값으로서 가능한 최대값

제약 조건

• $2 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 모든 값은 정수

입출력 예시

입력:

6
2 1 2 1 1 10

출력:

4
2

• 평균값 최대: 2번째, 4번째, 6번째 카드를 선택하면, 값은 {1, 1, 10}이고 평균 = $12/3 = 4$
• 중앙값 최대: 1번째, 3번째, 5번째, 6번째 카드를 선택하면, 값은 {2, 2, 1, 10}이고 중앙값 = (작은 순으로 $\lceil 4/2 \rceil = 2$번째) = 2

선택 조건 이해하기

"2장 연속으로 선택하지 않는 것은 불가"라는 조건을 확인합니다:

카드 번호:	1	2	3	4	5	6

✅ 유효:	○	×	○	×	○	○  (연속 미선택 없음)
✅ 유효:	○	○	○	○	○	○  (전부 선택)
✅ 유효:	×	○	×	○	×	○  (교대)
❌ 무효:	○	×	×	○	○	○  (2~3번이 연속 미선택)

Step 1 — 완전 탐색의 한계

가장 단순한 접근: 가능한 모든 선택 조합을 시도하고, 각 조합의 평균값과 중앙값을 계산하여 최댓값을 구합니다.

조합 수 계산

각 카드에 대해 "선택/미선택" 2가지이므로:

$\text{전체 조합 수} = 2^N$

$N = 10^5$일 때, $2^{100000}$은 처리 불가능합니다.

동적 계획법 직접 접근 (서적 1.3.1)

서적에서는 DP로 평균값 최대를 구하는 접근도 소개합니다:

• $dp[i][j][k]$ = i번째까지 카드 중 j장 선택, i번째 카드를 선택했는지(k=0/1)일 때의 평균값 최대
• 전이 시 $O(N)$가지의 j값 → 전체 O(N²)

$N = 10^5$일 때,  $10^{10}$ 연산으로 시간 초과입니다.

Step 2 — [평균값] 판정 문제로 변환하기

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

핵심 아이디어

원래 문제:

이를 다음과 같은 판정 문제로 바꿉니다:

수식 변형 — 핵심 관찰

k장의 카드를 선택했다고 합시다 ($a_1, a_2, \ldots, a_k$번째 카드). 평균값이 $X$ 이상이 되려면:

$\frac{A_{a_1} + A_{a_2} + \cdots + A_{a_K}}{K} \geq X$

양변에 $K$(양수)를 곱합니다:

$A_{a_1} + A_{a_2} + \cdots + A_{a_K} \geq KX$

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

$(A_{a_1} - X) + (A_{a_2} - X) + \cdots + (A_{a_K} - X) \geq 0$

핵심 정의

각 카드 $i$에 대해 새로운 값 $B_i$를 정의합니다:

$B_i = A_i - X$

그러면 판정 문제는:

$X$는 이분 탐색에서 고정된 값이므로, $B_i$는 단순한 뺄셈으로 계산됩니다. 남은 문제는 "조건을 만족하면서 B의 합계를 최대화"하는 것입니다.

단조성 확인

• $X$가 작을수록 $B_i = A_i - X$가 커지므로, 합계 ≥ 0을 달성하기 쉬움 → ✅
• $X$가 클수록 $B_i$가 작아지므로, 합계 ≥ 0을 달성하기 어려움 → ❌

✅/❌의 경계가 하나만 존재 → 이분 탐색 적용 가능!

Step 3 — [평균값] 합계 최대화 DP

Step 2에서 문제를 "배열에서 조건을 만족하며 합계를 최대화"로 변환했습니다. 이제 이 합계 최대화를 DP로 해결합니다.

선택 조건을 다시 확인

"2장 연속으로 선택하지 않는 것은 금지" → 각 카드에 대해 i번째를 선택했는지 여부가 다음 선택에 영향을 줍니다.

DP 정의

두 개의 배열 $S$와 $T$를 정의합니다:

• $S_{i+1}$ = B의 처음 $i$개까지 중, 조건을 만족하면서 $i$번째를 선택했을 때의 합계 최대값
• $T_{i+1}$ = B의 처음 $i$개까지 중, 조건을 만족하면서 $i$번째를 선택하지 않았을 때의 합계 최대값

초기값: $S_1 = 0,\ T_1 = 0$

점화식 도출

$S_{i+1}$을 구할 때 (i번째 카드를 선택):

• i-1번째를 선택했든 안 했든 상관없음 (i번째를 선택하므로 "2연속 미선택" 위반 없음)
• 따라서 $S_{i+1} = \max(S_i, T_i) + B_i$

$T_{i+1}$을 구할 때 (i번재 카드를 미선택):

• "2연속 미선택 금지"이므로, i-1번째는 반드시 선택되어 있어야 함
• 따라서 $T_{i+1} = S_i$

정리하면:

$S_{i+1} = \max(S_i, T_i) + B_i$

$T_{i+1} = S_i$

예시로 이해하기

$A = [2, 1, 2, 1, 1, 10]$, $X = 4$일 때, $B = [-2, -3, -2, -3, -3, 6]$

1	$B_i$	$S_{i+1}$	$T_{i+1}$
초기	—	$S+1=0$	$T_1=0$
1	-2	$\max(0,0)+(-2)=-2$	$0$
2	-3	$\max(-2,0)+(-3)=-3$	$-2$
3	-2	$\max(-3,-2)+(-2)=-4$	$-3$
4	-3	$\max(-4,-3)+(-3)=-6$	$-4$
5	-3	$\max(-6,-4)+(-3)=-7$	$-6$
6	6	$\max(-7,-6)+6=0$	$-7$

최종: $\max(S_7, T_7) = \max(0, -7) = 0 \geq 0$ → ✅ (평균값 4 이상 가능!)

Step 4 — [평균값] 판정 함수 + 이분 탐색

Step 3의 DP를 판정 함수로 구현합니다.

Java 코드 예시 — checkAverage

// A[] 는 외부에서 전달된다고 가정

static boolean checkAverage(int N, long[] A, double X) {
    // ── 1단계: B 배열 계산 ──
    double[] B = new double[N];
    for (int i = 0; i < N; i++) {
        B[i] = A[i] - X;
    }

    // ── 2단계: DP로 합계 최대화 ──
    double[] S = new double[N + 1];  // i번째를 선택
    double[] T = new double[N + 1];  // i번째를 미선택

    for (int i = 0; i < N; i++) {
        S[i + 1] = Math.max(T[i], S[i]) + B[i];
        T[i + 1] = S[i];
    }

    // ── 3단계: 합계 ≥ 0이면 판정 성공 ──
    return Math.max(S[N], T[N]) >= -1e-9;
}

각 단계의 의미

단계	코드	의미
1단계	B[i] = A[i] - X	각 카드의 "가치"를 현재 X 기준으로 계산
2단계	S/T DP	"2연속 미선택 금지" 조건하에서 B의 합계 최대화
3단계	max(S[N], T[N]) ≥ 0	합계 0 이상을 달성 가능하면, 평균값 X 이상 달성 가능

이분 탐색

평균값은 실수이므로, 반복 횟수를 고정하는 실수 이분 탐색을 사용합니다:

double lo = 0, hi = 1e10;  // A_i ≤ 10^9이므로 넉넉하게
for (int iter = 0; iter < 100; iter++) {
    double mid = (lo + hi) / 2.0;
    if (checkAverage(N, A, mid)) {
        lo = mid;   // mid 이상 가능 → 더 큰 값 탐색
    } else {
        hi = mid;   // mid 이상 불가능 → 더 작은 값 탐색
    }
}
// lo가 답

Step 5 — [중앙값] 판정 문제로 변환하기

이제 중앙값 최대화 문제를 풀어봅시다. 평균값과 같은 프레임워크를 사용하되, 변환 방식이 다릅니다.

핵심 아이디어

원래 문제:

이를 다음과 같은 판정 문제로 바꿉니다:

중앙값 ≥ X의 의미

K장의 카드를 선택했을 때, 중앙값이 $X$ 이상이 되려면:

이를 정확히 표현하면:

• K가 홀수일 때: $X$ 이상인 카드가 $\frac{K+1}{2}$개 이상
• K가 짝수일 때: $X$ 이상인 카드가 $\frac{K}{2}+1$개 이상

두 경우 모두 "$X$ 이상인 카드의 수 > $X$ 미만인 카드의 수"로 통일할 수 있습니다.

수식 변형 — ±1 변환

각 카드 $i$에 대해 새로운 값 $B_i$를 정의합니다:

$B_i = \begin{cases} +1 & \text{if } A_i \geq X \\ -1 & \text{if } A_i < X \end{cases}$

이렇게 변환하면:

• 선택한 카드 중 $X$ 이상인 카드의 수 = (선택한 $B$ 중 $+1$의 개수)
• 선택한 카드 중 $X$ 미만인 카드의 수 = (선택한 $B$ 중 $-1$의 개수)

따라서 "$X$ 이상이 더 많다"는 조건은:

$\text{(선택한 B의 합계)} > 0$

판정 문제는:

평균값 변환과의 비교

	평균값	중앙값
변환	$B_i = A_i - X$ (실수)	$B_i = \pm 1$ (정수)
판정 조건	합계 $\geq 0$	합계 $> 0$
X의 성질	실수	정수 (중앙값은 반드시 $A_i$ 중 하나)

Step 6 — [중앙값] 동일 DP 재활용

동일한 DP 구조

Step 3에서 도출한 S/T 점화식을 그대로 사용합니다:

$S_{i+1} = \max(S_i, T_i) + B_i$

$T_{i+1} = S_i$

예시로 이해하기

$A = [2, 1, 2, 1, 1, 10]$, $X = 2$일 때, $B = [1, -1, 1, -1, -1, 1]$

1	$B_i$	$S_{i+1}$	$T_{i+1}$
초기	—	$S+1=0$	$T_1=0$
1	1	$\max(0,0)+1=1$	$0$
2	-1	$\max(1,0)+(-1)=0$	$1$
3	1	$\max(0,1)+1=2$	$0$
4	-1	$\max(2,0)+(-1)=1$	$2$
5	-1	$\max(1,2)+(-1)=1$	$1$
6	1	$\max(1,1)+1=2$	$1$

최종: $\max(S_7, T_7) = \max(2, 1) = 2 > 0$ → ✅ (중앙값 2 이상 가능!)

Java 코드 예시 — checkMedian

static boolean checkMedian(int N, long[] A, long X) {
    // ── 1단계: B 배열 계산 (±1 변환) ──
    int[] B = new int[N];
    for (int i = 0; i < N; i++) {
        B[i] = (A[i] >= X) ? 1 : -1;
    }

    // ── 2단계: DP로 합계 최대화 (평균값과 완전히 동일) ──
    long[] S = new long[N + 1];
    long[] T = new long[N + 1];

    for (int i = 0; i < N; i++) {
        S[i + 1] = Math.max(T[i], S[i]) + B[i];
        T[i + 1] = S[i];
    }

    // ── 3단계: 합계 > 0이면 판정 성공 (≥ 0이 아닌 > 0!) ──
    return Math.max(S[N], T[N]) > 0;
}

이분 탐색

중앙값은 반드시 정수(원래 배열 $A$의 원소 중 하나)이므로, 정수 이분 탐색을 사용합니다:

long lo = 0, hi = 1_000_000_001L;  // A_i ≤ 10^9
while (hi - lo > 1) {
    long mid = (lo + hi) / 2;
    if (checkMedian(N, A, mid)) {
        lo = mid;   // mid 이상 가능 → 더 큰 값 탐색
    } else {
        hi = mid;   // mid 이상 불가능 → 더 작은 값 탐색
    }
}
// lo가 답

Step 7 — 완성 코드 예시

평균값(실수 이분 탐색)과 중앙값(정수 이분 탐색)을 통합한 최종 코드 예시입니다.

완성 Java 코드 예시

import java.util.*;

public class Main {
    static int N;
    static long[] A;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        A = new long[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextLong();

        // ===== 평균값 최대화 (실수 이분 탐색) =====
        double avLo = 0, avHi = 1e10;
        for (int iter = 0; iter < 100; iter++) {
            double mid = (avLo + avHi) / 2.0;
            if (checkAverage(mid)) {
                avLo = mid;
            } else {
                avHi = mid;
            }
        }
        System.out.printf("%.13f%n", avLo);

        // ===== 중앙값 최대화 (정수 이분 탐색) =====
        long mdLo = 0, mdHi = 1_000_000_001L;
        while (mdHi - mdLo > 1) {
            long mid = (mdLo + mdHi) / 2;
            if (checkMedian(mid)) {
                mdLo = mid;
            } else {
                mdHi = mid;
            }
        }
        System.out.println(mdLo);
    }

    // 평균값이 X 이상이 되는 선택 방법이 존재하는가?
    static boolean checkAverage(double X) {
        double[] B = new double[N];
        for (int i = 0; i < N; i++) B[i] = A[i] - X;

        double[] S = new double[N + 1];
        double[] T = new double[N + 1];
        for (int i = 0; i < N; i++) {
            S[i + 1] = Math.max(T[i], S[i]) + B[i];
            T[i + 1] = S[i];
        }
        return Math.max(S[N], T[N]) >= -1e-9;
    }

    // 중앙값이 X 이상이 되는 선택 방법이 존재하는가?
    static boolean checkMedian(long X) {
        int[] B = new int[N];
        for (int i = 0; i < N; i++) B[i] = (A[i] >= X) ? 1 : -1;

        long[] S = new long[N + 1];
        long[] T = new long[N + 1];
        for (int i = 0; i < N; i++) {
            S[i + 1] = Math.max(T[i], S[i]) + B[i];
            T[i + 1] = S[i];
        }
        return Math.max(S[N], T[N]) > 0;
    }
}

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

평균값 (실수 이분 탐색):

A = [2, 1, 2, 1, 1, 10]

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

중앙값 (정수 이분 탐색):

iter 0:		lo=0, hi=1000000001, mid=500000000 → check=false → hi=500000000
...
(범위가 급격히 줄어듦)
...
iter 28:	lo=2, hi=3    → check(2)=true, check(3)=false
iter 29:	lo=2, hi=3    → hi-lo=1 → 종료

출력: 2 ✅

두 이분 탐색의 비교

	평균값	중앙값
탐색 대상	실수 (연속)	정수 (이산)
종료 조건	반복 100회 고정	while (hi - lo > 1)
반복 횟수	정확히 100회	$\lceil \log_2(10^9) \rceil \approx 30$ 회
이유	답이 실수이므로 "정확히 일치"가 불가	답이 정수이므로 구간 길이 1이면 확정

Step 8 — 계산량 분석 & 정리

시간 복잡도

부분	계산량
checkAverage(X) 1회	$O(N)$ — B 계산 $O(N)$ + DP $O(N)$
평균값 이분 탐색	100회 x $O(N)$ = $O(N)$
checkMedian(X) 1회	$O(N)$ — B 계산 $O(N)$ + DP $O(N)$
중앙값 이분 탐색	$O(\log \max(A))$회 x $O(N)$ = $O(N \log \max(A))$
전체	$O(N \log \max(A))$

$N = 10^5$일 때: $10^5 \times (100 + 30) = 1.3 \times 10^7$ 정도의 연산으로, 시간 제한 내에 여유 있게 통과합니다.

Part 1 전체 3문제 비교

이 문제에서 배운 패턴

핵심 요약

항목	내용
문제 유형	평균값 최대화 + 중앙값 최대화 (조건부 선택)
접근법	최적화 → 판정 문제 변환 + 이분 탐색
핵심 변환	평균값: $B_i = A_i - X$ / 중앙값: $B_i = \pm 1$
판정 함수	"2연속 미선택 금지" 조건하에서 합계 최대화 DP — $O(N)$
이분 탐색 타입	평균값: 실수 (100회) / 중앙값: 정수 (while)
계산량	$O(N \log \max(A))$

관련 링크

• Part 1 본문: 이분 탐색 심화 — 이 문제를 포함한 3가지 이분 탐색 기법의 전체 정리
• 문제 URL: [AtCoder Beginner Contest 236] — E - Average and Median
• 소스코드: tsutaj/pastbook-2-source-code (Github)