백준 2512 파이썬 예산 문제

백준 2512번 예산 문제를 통해 알아보는 이분 탐색과 파라메트릭 서치의 완벽 이해와 활용법에 대한 상세 요약입니다.

1. 📋 문제 개요와 핵심 조건

• 국가의 역할은 여러 지방의 예산요청을 심사하여 국가 예산을 분배하는 것이다
• 예산 배정 규칙:
  – 모든 요청이 배정 가능한 경우: 요청한 금액을 그대로 배정
  – 모든 요청이 배정 불가능한 경우: 정수 상한액을 계산하여 초과분은 상한액만 배정
  – 상한액 이하의 요청은 요청한 금액 그대로 배정

1.1. 문제 입출력 예시

– 예제 입력 1:

• 지방 수: 4
• 각 예산 요청: 120, 110, 140, 150
• 총예산: 485
• 출력: 127 (상한액)

– 예제 입력 2:

• 지방 수: 5
• 각 예산 요청: 70, 80, 30, 40, 100
• 총예산: 450
• 출력: 100 (상한액)

2. 🧩 문제 이해와 접근 전략

– 이 문제의 핵심 질문: “가능한 최대의 상한액은 얼마인가?”
– 상한액의 특성: 상한액보다 적게 요청한 지방은 요청 금액 그대로, 많이 요청한 지방은 상한액만 받음
– 예제 1의 경우: 상한액을 127로 설정하면 120, 110, 127, 127로 배정하여 총 484로 최적8

2.1. 브루트포스 접근법의 한계

• 상한액을 1부터 차례로 증가시키며 시뮬레이션하는 방법
• 문제점: 비효율적
  – 최대 요청액이 100,000까지 가능하므로 시간 복잡도 O(N×M)에서 시간 초과 발생5

3. 🎯 파라메트릭 서치 접근법

3.1. 파라메트릭 서치의 개념

파라메트릭 서치란 최적화 문제를 결정 문제로 변환하여 푸는 기법이다513.

• 최적화 문제: 정해진 총액(M) 이하에서 최대 상한액(K)은 얼마인가?
• 결정 문제: 상한액이 K일 때 총 배정액이 M 이하가 되는가? (Yes/No)8

3.2. 이분 탐색과 파라메트릭 서치의 차이

– 이분 탐색: 정렬된 배열에서 특정 값을 찾는 알고리즘9
– 파라메트릭 서치: 주어진 범위 내에서 조건을 만족하는 값을 찾는 알고리즘9
– 파라메트릭 서치는 정렬이 필수 조건이 아닌 점이 다름8

4. 💻 알고리즘 구현 방법

4.1. 이분 탐색 구현 골격

def binary_search(array, value, low, high):
    if low > high:
        return False
    mid = (low + high) // 2
    if array[mid] > value:
        return binary_search(array, value, low, mid-1)
    elif array[mid] < value:
        return binary_search(array, value, mid+1, high)
    else:
        return mid

4.2. 예산 문제 파라메트릭 서치 구현

import sys
input = sys.stdin.readline

N = int(input())  # 지방의 수
req = list(map(int, input().split()))  # 각 지방 예산 요청
M = int(input())  # 총 예산

low = 0  # 탐색 범위 시작점
high = max(req)  # 탐색 범위 종료점 (최대 요청액)
ans = 0  # 결과값

def is_possible(mid):
    # 상한액이 mid일 때 배정 가능한지 확인
    return sum(min(r, mid) for r in req) <= M

while low <= high:
    mid = (low + high) // 2
    if is_possible(mid):  # 배정 가능하면
        low = mid + 1  # 상한액을 높이기
        ans = mid  # 가능한 값 저장
    else:  # 배정 불가능하면
        high = mid - 1  # 상한액을 낮추기
    
print(ans)

4.3. 핵심 함수 분석: is_possible()

• 상한액(mid)이 주어졌을 때 가능한지 판단하는 함수4
• 각 지방별로 요청액과 상한액 중 작은 값을 배정
• 총합이 국가 예산(M) 이하면 가능함을 반환12

5. 🔄 알고리즘 동작 과정

5.1. 예제 1의 실행 흐름

1. 초기 설정: low=0, high=150(최대 요청), ans=0
2. 1단계: mid=75
   – 75로 배정 시 합계는 75+75+75+75=300 < 485
   – 가능함: low=76, ans=75
3. 2단계: mid=113
   – 113 배정 시 합계: 120+110+113+113=456 < 485
   – 가능함: low=114, ans=113
4. 3단계: mid=126
   – 126 배정 시 합계: 120+110+126+126=482 < 485
   – 가능함: low=127, ans=126
5. 4단계: mid=127
   – 127 배정 시 합계: 120+110+127+127=484 < 485
   – 가능함: low=128, ans=127
6. 5단계: mid=128
   – 128 배정 시 합계: 120+110+128+128=486 > 485
   – 불가능: high=127
7. 종료: low=129, high=127로 low>high 조건으로 종료
   – 정답: ans=127

6. 🧠 파라메트릭 서치 설계 원칙

6.1. 성공 조건

1. 결정 문제를 쉽게 풀 수 있어야 함5
2. 가능한 해의 영역이 연속적이어야 함13
   – TTTT…FFFF… 또는 FFFF…TTTT… 형태

6.2. 구현 시 주의사항

• 시작값(low)과 끝값(high) 설정이 중요함10
• 정답이 항상 마지막 탐색 지점(high)이 아닐 수 있음13
• 조건을 만족할 때 정답 갱신 후 범위 조정해야 함8

7. 📊 시간 복잡도 분석

• 브루트포스: O(N×M) → 최대 10,000×100,000 = 10억 연산 필요5
• 파라메트릭 서치: O(N×log M) → 10,000×log(100,000) ≈ 10,000×17 = 17만 연산5
• 1초 제한에서 연산 상한은 약 1억이므로 파라메트릭 서치만 시간 내 해결 가능5

8. 📚 유사 문제와 응용

• 백준 2805번: 나무 자르기5
• 백준 2470번: 두 용액5
• 파라메트릭 서치는 최적화 문제를 결정 문제로 변환할 수 있는 다양한 상황에 적용 가능13

9. 🔑 결론

파라메트릭 서치는 단순한 이분 탐색의 응용이 아닌, 최적화 문제를 효율적으로 해결하는 강력한 알고리즘 기법이다. 백준 2512번 예산 문제는 이 기법의 전형적인 응용 사례로, 최적화 문제를 결정 문제로 변환하여 효율적으로 해결하는 패러다임을 보여준다12. 상한액이라는 파라미터를 조정하며 가능성을 판단하는 과정이 파라메트릭 서치의 본질이며, 이를 통해 큰 탐색 공간도 로그 시간에 처리할 수 있다5.

Citations:

1. https://sarah950716.tistory.com/16
2. http://subinium.github.io/Algorithm/docs/chapter03/4.html
3. https://great-park.tistory.com/44
4. https://yes6686.tistory.com/195
5. https://velog.io/@lake/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89-%ED%8C%8C%EB%9D%BC%EB%A9%94%ED%8A%B8%EB%A6%AD-%EC%84%9C%EC%B9%98Parametric-Search
6. https://codingsmu.tistory.com/135
7. https://velog.io/@wjdrbs786/Java-%EB%B0%B1%EC%A4%80-BOJ-2512%EB%B2%88-%EC%98%88%EC%82%B0
8. https://loosie.tistory.com/552
9. https://marades.tistory.com/7
10. https://tooo1.tistory.com/129
11. https://alive-wong.tistory.com/68
12. https://spookyjelly.tistory.com/36
13. https://9327144.tistory.com/entry/%ED%8C%8C%EB%9D%BC%EB%A9%94%ED%8A%B8%EB%A6%AD-%EC%84%9C%EC%B9%98Parametric-Search
14. https://velog.io/@zerohyun__/%EB%B0%B1%EC%A4%80-2512
15. https://blog.naver.com/jinhan814/222156334908
16. https://www.acmicpc.net/problem/2512
17. https://velog.io/@sorzzzzy/Algorithm-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89-%ED%8C%8C%EB%9D%BC%EB%A9%94%ED%8A%B8%EB%A6%AD-%EC%84%9C%EC%B9%98
18. https://m42-orion.tistory.com/70
19. https://loosie.tistory.com/518
20. https://david0506.tistory.com/2
21. https://ialy1595.github.io/post/parametric-search/
22. https://amepistheo.tistory.com/5
23. https://velog.io/@sh93/%EB%B0%B1%EC%A4%80-2512%EB%B2%88-%EC%98%88%EC%82%B0-.-python
24. https://jy-tblog.tistory.com/36
25. https://chanmuzi.tistory.com/237
26. https://sdy-study.tistory.com/90
27. https://stdio-han.tistory.com/112
28. https://beginthread.tistory.com/30
29. https://claude-u.tistory.com/447
30. https://velog.io/@nuri00/%EB%B0%B1%EC%A4%80-2512%EB%B2%88-%EC%98%88%EC%82%B0
31. https://ulwunr.tistory.com/11