그리디와 문제해결

그리디의 세 가지 흔한 패턴

1) 정렬 후 순서대로 선택

대부분의 그리디는 "무엇을 기준으로 정렬하느냐"가 전부입니다. 기준을 정하면
한 번 훑으며 선택합니다.

// 예: 마감(deadline) 안에 최대 이득 — 마감 늦은 순 등 문제별 기준
sort(jobs.begin(), jobs.end(), cmp);
for (auto& j : jobs) { /* 조건 되면 선택 */ }

2) 우선순위 큐(힙)로 매 순간 최선 뽑기

"현재 가장 작은/큰 것을 꺼내 처리"가 반복되면 힙을 씁니다. 파일 합치기(항상
가장 작은 두 개를 합침), 최소 스패닝 트리의 프림 등.

priority_queue<long long, vector<long long>, greater<>> pq(a.begin(), a.end());
long long cost = 0;
while (pq.size() > 1) {
    long long x = pq.top(); pq.pop();
    long long y = pq.top(); pq.pop();
    cost += x + y;                    // 가장 작은 두 개를 합침
    pq.push(x + y);
}

import heapq
heapq.heapify(a)
cost = 0
while len(a) > 1:
    x = heapq.heappop(a)
    y = heapq.heappop(a)
    cost += x + y
    heapq.heappush(a, x + y)

3) 교환/부등식 기준 정렬

"두 원소 \(a\), \(b\)의 처리 순서를 \(a{+}b\) vs \(b{+}a\)처럼 비교해 결정"하는
유형. 정렬 비교 함수에 그 부등식을 넣습니다(문자열 이어 붙여 최대 수 만들기,
작업 스케줄링 등). Python은 functools.cmp_to_key를 씁니다.

정당성 검증: 반례로 무너뜨려 보기

그리디를 코딩하기 전에 반례를 찾으려 시도하세요. 못 찾으면 교환 논증으로
증명을 시도합니다. 특히 다음을 점검:

• 지금 최선을 고르면 미래에 더 큰 손해가 생기는 입력이 있는가?
• 여러 정렬 기준 중 어느 것이 옳은가? (기준을 바꾸면 답이 달라지는지 실험)

브루트포스로 검증(스트레스 테스트)

작은 \(N\)에서 완전 탐색과 그리디의 답을 무작위 입력으로 비교하면, 틀린 그리디를
빠르게 걸러낼 수 있습니다. 다음 강에서 이 검증 코드를 다룹니다.

그리디의 가장 큰 위험: "그럴듯하지만 틀림"

그리디는 코드가 짧아 매력적이지만, 증명 없이 제출하면 위험합니다. 지역적
최선이 전역 최적을 보장하지 않는 경우가 아주 많습니다.

• 동전(거스름돈): 화폐가 \(\{1, 3, 4\}\)면 큰 것부터 그리디가 틀립니다. 임의
  화폐는 DP가 정답.
• 0/1 배낭: 단위 가치가 큰 것부터 담는 그리디는 틀립니다(분할 가능 배낭은
  그리디가 맞지만, 0/1은 DP).
• 최장 경로/일반 스케줄링: 순진한 그리디가 반례에 무너지기 쉽습니다.

스트레스 테스트로 반례 자동 탐색

작은 입력에서 완전 탐색(정답) 과 그리디를 비교해 불일치를 찾습니다.

import random, itertools

def brute(coins, target):                # 최소 동전 수 (완전 탐색/DP)
    INF = float("inf")
    dp = [0] + [INF] * target
    for t in range(1, target + 1):
        for c in coins:
            if c <= t:
                dp[t] = min(dp[t], dp[t - c] + 1)
    return dp[target]

def greedy(coins, target):               # 큰 동전부터 (틀릴 수 있음)
    cnt, t = 0, target
    for c in sorted(coins, reverse=True):
        cnt += t // c
        t %= c
    return cnt if t == 0 else float("inf")

for _ in range(10000):
    coins = random.sample(range(1, 10), 3) + [1]  # 1 포함 보장
    target = random.randint(1, 30)
    if brute(coins, target) != greedy(coins, target):
        print("반례:", coins, target,
              brute(coins, target), greedy(coins, target))
        break

이 패턴 하나로 "그럴듯한 그리디"의 오류를 실전 제출 전에 잡아낼 수 있습니다.

그리디 vs DP — 언제 무엇을

그리디가 옳다는 확신이 없으면 DP로 후퇴하는 것이 안전합니다. 반대로 DP가
너무 느릴 때 문제 구조가 교환 논증을 허용하면 그리디로 최적화합니다.

흔한 함정

• 증명 생략 — 반례 없이 "맞겠지"로 제출 → 오답. 반드시 검증.
• 잘못된 정렬 기준 — 여러 기준 중 옳은 하나를 실험/증명으로 확정.
• 오버플로 — 비용 누적은 long long.
• 동점 처리 — 정렬에서 같은 키의 2차 기준을 놓치면 특정 입력에서 실패.
• 되돌림이 필요한 문제 — 그리디로 안 되면 DP나 매칭 등으로 전환.

요약

그리디는 "매 순간 최선 + 되돌리지 않음"이라는 단순한 전략이지만, 교환
논증으로 정당성을 확인하고 스트레스 테스트로 반례를 배제하는 습관이
그리디를 안전하게 만듭니다. 정렬·힙·교환 기준이라는 세 패턴을 익히고, 확신이
없으면 DP를 택하세요.

불변량으로 "불가능"을 증명하기

어떤 목표 상태에 도달할 수 없음을 보이는 가장 강력한 도구가 불변량
입니다. 허용된 연산이 어떤 양을 절대 바꾸지 않는다면, 그 양이 다른 두 상태는
서로 오갈 수 없습니다.

• 체스판 색칠: \(8 \times 8\) 판에서 대각 반대편 두 칸을 제거하고 도미노로
  덮기 — 흑백 개수가 어긋나 불가능. 각 도미노는 흑1·백1을 덮는다는 불변량.
• 15-퍼즐: 목표 배치의 역전 수 패리티가 맞지 않으면 도달 불가.
• 동전 뒤집기/토글: 특정 위치들의 XOR(합의 홀짝)이 불변이면 목표 판정.

관찰 훈련: "이 연산을 했을 때 변하지 않는 것이 무엇인가?"를 항상 물으세요.

극단 원소로 구조 잡기

가장 큰(또는 작은) 원소를 먼저 고정하면 나머지 구조가 단순해지는 경우가
많습니다.

• 최댓값은 반드시 특정 위치에 있어야 한다 → 경우가 줄어든다.
• 정렬 후 양 끝(최대·최소)부터 짝지으면 최적 배치가 드러난다.

역방향·여집합으로 세기

"조건을 만족하는 것"을 세기 어렵다면 전체 \(-\) (조건을 어기는 것) 이 쉬운지
보세요. "적어도 하나"는 여집합("하나도 없음")을 빼는 것이 정석입니다.

구성적 관찰의 예: 홀짝 배치

"\(1 \dots N\)을 인접한 두 수의 차가 모두 같지 않도록 배열하라" 같은 구성
문제는, 홀수끼리·짝수끼리 묶어 배치하는 관찰로 곧장 답이 나옵니다. 작은
\(N\)에서 손으로 하나 만들어 보면 패턴이 보입니다.

# 관찰: 홀수 먼저, 그다음 짝수 (인접 차가 2 또는 큰 값이라 조건 회피)
def construct(N):
    return [x for x in range(1, N + 1) if x % 2 == 1] + \
           [x for x in range(1, N + 1) if x % 2 == 0]

사고 루틴 요약

1. 작은 \(N\)을 직접/브루트포스로 풀어 표를 만든다.
2. 표에서 패턴·불변량·패리티를 찾는다.
3. 추측을 세우고 브루트포스와 대조 검증한다.
4. 검증되면 공식/구성으로 코딩한다.

애드 혹의 최대 함정: 검증 없는 추측

애드 혹은 "관찰"이 핵심이지만, 관찰이 틀린 추측일 수 있습니다. 작은
경우 몇 개만 맞아떨어져 성급히 일반화했다가 큰 입력에서 무너지는 일이 흔합니다.

방어책: 스트레스 테스트

추측한 공식/구성을, 작은 범위에서 완전 탐색(정의대로 계산) 과 무작위
입력으로 대조합니다. 불일치가 나오면 관찰이 틀린 것입니다.

import random

def brute(args):
    # 문제 정의를 그대로 구현 (느려도 정확)
    ...

def guess(args):
    # 관찰로 얻은 빠른 풀이 (틀릴 수 있음)
    ...

for _ in range(100000):
    args = random_small_case()           # 작은 무작위 입력
    if brute(args) != guess(args):
        print("반례 발견:", args, brute(args), guess(args))
        break
else:
    print("10만 케이스 통과 — 관찰이 옳을 가능성 높음")

"통과"가 증명은 아니지만, 틀린 관찰을 걸러내는 데는 매우 효과적입니다.

흔한 함정 정리

• 작은 경우 과적합 — \(N \le 3\)만 맞는 우연한 규칙을 일반화. 범위를 넓혀 검증.
• 경계값 무시 — \(N = 0, 1\), 빈 입력, 최댓값 등 극단 케이스에서 공식이 깨짐.
• 오버플로 — 조합·곱셈 공식은 값이 폭발. long long이나 모듈러.
• 불변량 오판 — "변하지 않는다"고 믿었는데 특정 연산이 바꾸는 경우. 다시 점검.
• 홀짝/모듈러 조건 누락 — 구성 문제에서 특정 \(N\)(홀수/짝수)만 가능/불가능인
  경우를 놓침.

관찰이 안 보일 때

• 브루트포스 출력 수열을 정수 수열로 검색하거나(OEIS 스타일 사고), 차분·비를
  살펴 규칙을 추정.
• 문제의 제약(N 크기) 을 복잡도로 역산해 어떤 종류의 답(공식/\(O(N)\)/$O(N
  \log N)$)이 기대되는지 가늠(종합 전략 단원 참고).
• 대칭·불변량·극단을 차례로 대입해 본다.

요약

애드 혹은 "작은 경우로 관찰 → 불변량/패리티/극단으로 일반화 → 스트레스
테스트로 검증"이라는 순환입니다. 표준 알고리즘이 없는 대신, 관찰을 찾는
도구 상자와 추측을 검증하는 습관이 실력을 좌우합니다.

구현 — 안전한 난수부터

1. C++ — mt19937, 시드, 균등 분포

rand() 는 품질·범위가 나빠 대회에서 지양합니다. mt19937(64비트는 mt19937_64) 를 쓰고, 시간+주소 로 시드해 예측을 어렵게 합니다.

#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(
    chrono::steady_clock::now().time_since_epoch().count());

long long randint(long long lo, long long hi) {          // [lo, hi]
    return uniform_int_distribution<long long>(lo, hi)(rng);
}

2. Fisher–Yates 셔플 (편향 없는 유일한 방법)

template <class T>
void shuffle_vec(vector<T>& a) {
    for (int i = (int)a.size() - 1; i > 0; i--) {
        int j = uniform_int_distribution<int>(0, i)(rng); // 0..i 포함
        swap(a[i], a[j]);
    }
}

j 를 0..n-1 로 뽑으면 편향이 생깁니다. 반드시 0..i. C++ 표준 std::shuffle(a.begin(), a.end(), rng) 를 써도 됩니다(random_shuffle 은 제거됨).

3. 다항 문자열 해시 (무작위 밑 + 이중 해시)

struct Hasher {
    const long long M1 = 1000000007, M2 = 998244353;
    long long B1, B2;
    vector<long long> h1, h2, p1, p2;
    Hasher(const string& s) {
        mt19937_64 r(chrono::steady_clock::now().time_since_epoch().count());
        B1 = 131 + r() % 1000; B2 = 137 + r() % 1000;    // 무작위 밑
        int n = s.size();
        h1.assign(n+1,0); h2.assign(n+1,0);
        p1.assign(n+1,1); p2.assign(n+1,1);
        for (int i = 0; i < n; i++) {
            h1[i+1] = (h1[i]*B1 + s[i]) % M1;
            h2[i+1] = (h2[i]*B2 + s[i]) % M2;
            p1[i+1] = p1[i]*B1 % M1;
            p2[i+1] = p2[i]*B2 % M2;
        }
    }
    // s[l..r] 해시(0-index, 양끝 포함) -> 두 값을 묶어 반환
    pair<long long,long long> get(int l, int r) {
        long long a = (h1[r+1] - h1[l]*p1[r-l+1]) % M1; if (a<0) a+=M1;
        long long b = (h2[r+1] - h2[l]*p2[r-l+1]) % M2; if (b<0) b+=M2;
        return {a, b};
    }
};

4. Python — 표본추출·셔플

import random
random.seed()                       # OS 엔트로피로 시드

def majority_element(a, tries=40):  # 몬테카를로: 과반 원소 찾기
    n = len(a)
    for _ in range(tries):
        x = random.choice(a)
        if a.count(x) * 2 > n:
            return x
    return None                     # tries번 실패 확률 < 2^-tries

random.shuffle(a)                   # 편향 없는 표준 셔플
sample = random.sample(a, k)        # 비복원 무작위 표본 k개

5. 요점

• 난수 품질: mt19937(_64), 시간 시드 — rand() 금지.
• 셔플: Fisher–Yates(0..i) 또는 std::shuffle.
• 해시: 무작위 밑 + 큰 소수 + 이중 해시 로 충돌 확률 \(\approx 1/(M_1 M_2)\).

심화·변형 — 랜덤화를 신뢰하려면

1. 안티해시 대비 (가장 중요한 함정)

고정된 밑 \(B\) 와 모듈러 \(M\) 을 쓰면, 출제자가 그 값에 맞춰 충돌 쌍(anti-hash test) 을 만들어 낼 수 있습니다(해시 해킹). 방어:

• 밑 \(B\) 를 실행마다 무작위 로(위 구현). 상대가 미리 충돌을 못 만듭니다.
• 이중 해시: 서로 다른 \((B, M)\) 두 벌. 동시에 충돌할 확률 \(\approx 1/(M_1 M_2) \sim 10^{-18}\).
• \(M\) 은 큰 소수. \(2^{64}\) 자연 오버플로 단일 해시는 Thue–Morse 류 반례에 취약하니 대회에선 피하거나 무작위 밑과 병용.

$$ P(\text{두 문자열 충돌}) \approx \frac{1}{M_1 M_2}\ (\text{독립 가정}) $$

2. 오류 확률을 반드시 정량화

몬테카를로는 "대충 맞겠지" 가 아니라 수치로 오류를 눌러야 합니다.

• \(q\) 쌍을 비교하면 충돌 확률은 생일 역설 로 대략 \(q^2/(2M)\) — 쌍의 수가 많으면 커집니다. \(M\) 을 충분히 크게(\(10^{18}\) 급, 이중 해시) 잡으세요.
• 반복 가능한 판정(밀러–라빈 등)은 독립 시행 \(k\)회 로 \(\varepsilon^k\) 까지 감소.

3. 라스베이거스는 답이 항상 옳다

퀵셀렉트·랜덤 피벗은 결과가 항상 정확하고 시간만 무작위입니다. "확률적으로 틀릴 수 있음" 은 몬테카를로에만 해당 — 둘을 혼동해 "정답이 틀릴 수도 있다" 고 잘못 말하지 마세요.

4. 셔플·난수 함정

• 편향 셔플: j = rng()%n 을 매 반복 고정 범위로 뽑으면 균등하지 않음 → 반드시 0..i.
• 모듈러 편향: rng() % k 는 \(k\) 가 범위를 나누어떨어지지 않으면 미세 편향 → uniform_int_distribution 사용.
• 시드 고정: 디버깅엔 고정 시드가 좋지만, 제출 시엔 시간 기반 시드 로 예측 회피.
• 재현성: 랜덤 실패를 디버깅하려면 사용한 시드를 로그로 남기세요.

5. 대표 랜덤화 알고리즘 지도

6. 요약

랜덤화의 힘은 "적대적 입력을 확률 사건으로 바꾸는 것" 입니다. 단, 반드시 (1) 좋은 난수원, (2) 무작위/이중 해시로 안티해시 방어, (3) 오류 확률의 정량화 세 가지를 지켜야 신뢰할 수 있는 해가 됩니다.

시간 예산: 대략 1초에 1억 연산

대회 판정기는 대략 초당 \(10^8 \sim 10^9\) 기본 연산을 처리합니다. 시간
제한과 \(N\)을 함께 보면 허용 복잡도가 나오고, 거기서 알고리즘 종류가
좁혀집니다.

제약 → 복잡도 → 기법 표

사용법: 문제의 \(N\)을 표에서 찾아 허용 복잡도를 읽고, 그 예산에 맞는
기법만 후보로 남깁니다. 예를 들어 \(N = 2\times10^5\)에 시간 2초면 \(O(N^2)\)
(\(4\times10^{10}\))는 불가능, \(O(N \log N)\)(\(\approx 3.6\times10^6\))은 넉넉함 —
정렬·이분·세그먼트 트리 계열을 우선 고려합니다.

메모리 예산

정수 배열은 원소당 4바이트(int)/8바이트(long long). \(256\)MB면 int
약 \(6\times10^7\)개가 상한 감각입니다. 2차원 배열 \(N \times N\)은 \(N = 5000\)이면
\(2.5\times10^7\)개 — int로 100MB. 제약에서 메모리도 역산하세요.

상수와 언어

• 같은 \(O(N \log N)\)이라도 상수가 다릅니다. C++은 여유롭고, Python은
  대략 \(10{\sim}50\)배 느리니 \(N\)이 크면 입출력·구현을 최적화하거나 pypy 감각으로.
• 입출력이 큰 문제는 빠른 입출력(C++ ios::sync_with_stdio(false),
  Python sys.stdin)이 필수입니다.

int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); /* ... */ }

import sys
input = sys.stdin.readline           # 큰 입력 필수

복잡도 역산 예시

"\(N \le 18\), 각 정점을 한 번씩 방문하는 최소 비용" → \(N \le 18\)이 곧
\(O(2^N\ N^2)\) 비트마스크 DP(외판원)를 가리킵니다. 제약이 알고리즘을
지목하는 전형입니다.

구현 후가 진짜 시작

풀이를 떠올렸어도 엣지 케이스와 버그가 오답을 만듭니다. 체계적 검증이
없으면 "왜 틀렸는지 모르는" 늪에 빠집니다.

엣지 케이스 체크리스트

• 최소 입력: \(N = 0, 1\), 빈 배열, 원소 하나.
• 최대 입력: 상한 크기에서 시간·오버플로 확인.
• 극단 값: 모두 같은 값, 이미 정렬됨, 역정렬, 음수/0.
• 경계: 구간 양 끝, 인덱스 off-by-one.
• 오버플로: 합·곱이 int를 넘는가 → long long.

스트레스 테스트(무작위 대조)

가장 강력한 디버깅 도구. 느리지만 확실한 브루트포스와 빠른 풀이를
무작위 입력으로 대조해 첫 반례를 자동으로 찾습니다.

import random

def brute(data):        # 정의대로 (느려도 정확)
    ...

def fast(data):         # 제출할 풀이 (검증 대상)
    ...

def random_case():
    n = random.randint(1, 8)             # 작게!
    return [random.randint(-5, 5) for _ in range(n)]

for t in range(100000):
    data = random_case()
    b, f = brute(data), fast(data)
    if b != f:
        print("반례:", data)
        print("brute =", b, " fast =", f)
        break
else:
    print("통과")

입력을 작게 잡는 것이 요령입니다 — 반례는 대개 작은 케이스에서도 나오고,
작아야 브루트포스가 감당합니다. 반례를 얻으면 손으로 추적해 버그를 고칩니다.

디버깅 절차

1. 예제부터 — 주어진 예제가 통과하는가. 안 되면 이해/구현 오류.
2. 직접 만든 엣지 케이스 — 체크리스트대로.
3. 스트레스 테스트 — 반례 자동 탐색.
4. 부분 검증 — 중간 값(접두사 합, 상태)을 stderr로 찍어 가정 확인.

cerr << "dbg mid=" << mid << " cnt=" << cnt << "\n";   // 채점에 안 보임

흔한 실패 원인 총정리

• 복잡도 오판 — 표로 역산 안 해 TLE. 제출 전 복잡도를 곱해 확인.
• 오버플로 — 32비트 초과. 합·곱은 long long.
• 엣지 케이스 — \(N = 0, 1\), 빈 입력, 경계.
• 입출력 지연 — 큰 입력에 느린 I/O로 TLE. 빠른 입출력 사용.
• 증명 없는 그리디/추측 — 반례에 무너짐. 스트레스 테스트로 검증.
• 인덱스 off-by-one — 구간·배열 경계. 한 표기법으로 통일.

전체 요약

종합 전략은 곧 재현 가능한 루틴입니다: 정확히 읽고 → 작은 경우 실험 →
제약으로 복잡도 역산 → 후보 알고리즘 → 정당성 검증 → 구현 → 스트레스
테스트. 이 순환을 반복하면 처음 보는 문제도 흔들림 없이 분해할 수 있습니다.

구성 문제란

구성(constructive) 문제 는 "조건을 만족하는 예시 하나를 만들어 내라"는
유형입니다. 최적화가 아니라 가능한 답 하나(또는 불가능 판정)를 출력합니다.

• "합이 \(S\)이고 서로 다른 \(K\)개의 수를 만들어라."
• "이런 성질을 가진 순열/그래프/격자를 구성하라. 없으면 \(-1\)."

핵심: 존재 증명이 곧 구성법

구성 문제는 "왜 이렇게 만들면 항상 되는가"의 증명이 알고리즘 그 자체입니다.
증명 과정에서 나온 명시적 절차를 그대로 코드로 옮깁니다.

• 먼저 작은 경우로 하나 만들어 본다(애드 혹과 동일).
• 규칙(홀짝, 등차, 재귀적 결합)을 찾아 일반 \(N\)의 구성법으로 승격.
• 불가능 조건(패리티, 합의 최소/최대 한계)을 먼저 걸러낸다.

예: 합이 S인 서로 다른 양의 정수 K개

가능 조건은 최소합 \(1 + 2 + \dots + K = \dfrac{K(K+1)}{2} \le S\). 가능하면
\(1, 2, \dots, K\)로 시작해 부족분을 가장 큰 원소에 몰아 줍니다.

def construct(S, K):
    if K * (K + 1) // 2 > S:
        return None                      # 불가능
    a = list(range(1, K + 1))            # 1..K
    a[-1] += S - sum(a)                  # 부족분을 마지막(최댓값)에 더함
    return a                             # 서로 다름 + 합 = S 보장

마지막 원소에 몰아 주면 여전히 서로 다름이 유지된다는 점이 증명의 핵심이며,
그 논리가 곧 코드입니다.

출력 빌더 패턴

구성 결과가 크면(격자·수열) 문자열을 모아 한 번에 출력해 I/O 비용을 줄입니다.

string out;
for (int i = 0; i < n; i++) out += to_string(ans[i]) + " ";
cout << out << '\n';

로컬 체커로 구성 검증

구성한 답이 정말 조건을 만족하는지 자동 검사하는 습관을 들이세요.

def check(a, S, K):
    return len(a) == K and len(set(a)) == K and all(x > 0 for x in a) and sum(a) == S

import random
for _ in range(100000):
    K = random.randint(1, 20)
    S = random.randint(1, 500)
    a = construct(S, K)
    if a is None:
        assert K * (K + 1) // 2 > S      # 불가능 판정이 옳은지
    else:
        assert check(a, S, K)            # 구성이 정말 유효한지

구성의 정당성과 불가능 판정을 모두 검증하는 것이 핵심입니다.

인터랙티브의 함정

• flush 누락 — 최대 원인. 매 질의 후 endl/flush=True. 안 하면 교착 →
  시간 초과처럼 보임.
• 판정기 답 읽기 누락 — 질의만 보내고 응답을 안 읽으면 다음 질의와 꼬입니다.
  질의 1개당 응답 1개를 정확히 주고받으세요.
• 질의 수 초과 — 상한을 넘으면 오답. 이분 탐색 등으로 \(O(\log N)\) 보장.
• 적응적 판정기 오해 — 정답이 고정됐다고 가정하는 전략 금지. 최악을 가정.
• 표준 입출력 혼선 — 디버그 출력을 stdout에 찍으면 판정기가 질의로 오해.
  디버그는 반드시 stderr로.

import sys
print("debug info", file=sys.stderr)     # 판정기에 안 보임 (안전)

구성 문제의 함정

• 불가능 판정 누락 — "없으면 \(-1\)"인데 항상 만들려다 실패. 최소/최대 한계와
  패리티를 먼저 검사.
• 경계 \(N\) — \(N = 1, 2\) 등 작은 경우에서 일반 규칙이 깨짐. 별도 처리.
• "서로 다름/범위" 조건 위반 — 몰아주기·재배치가 조건을 깨지 않는지 증명·검증.
• 여러 정답 허용 — 대개 아무 유효 답이나 정답. 특정 형태를 고집할 필요 없음.
• 오버플로 — 합·곱 한계 계산 시 long long.

두 유형의 공통 사고 루틴

인터랙티브와 구성은 모두 애드 혹적 관찰 + 엄밀한 증명을 요구합니다.

1. 작은 경우를 직접 해 보며 전략/구성 규칙을 찾는다.
2. 불변량·패리티·정보 이론적 하한으로 가능/불가능과 질의 수를 가늠한다.
3. 규칙을 일반 \(N\)으로 승격하고, 로컬 체커/브루트포스로 검증한다.
4. (인터랙티브) flush와 응답 읽기를 정확히. (구성) 불가능 판정과 경계를 먼저.

정보 이론적 하한 감각

인터랙티브에서 "가능한 답이 \(M\)가지, 질의 한 번이 답을 \(b\)갈래로 나눈다면 최소
\(\log_b M\)번"이라는 하한 감각이 전략 설계에 유용합니다. 예: 이진 응답이면
\(\lceil \log_2 M \rceil\)번이 하한 — 이분 탐색이 최적임을 알 수 있습니다.

요약

인터랙티브는 "질의 전략 + flush/응답 규율", 구성은 "존재 증명이 곧
구성법 + 불가능 판정"입니다. 두 유형 모두 작은 경우 관찰과 로컬 검증으로
발상을 다지고, 각자의 대표 함정(교착 / 불가능 누락)만 피하면 됩니다.