흰 스타렉스에서 내가 내리지

Parametric Search의 전형적인 문제 - BOJ2805 본문

Problem Solving

Parametric Search의 전형적인 문제 - BOJ2805

주씨. 2023. 12. 26. 20:48
728x90

https://www.acmicpc.net/problem/2805

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

 

 

# Parametric Search

- 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 

- '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 파라메트릭 서치를 사용한다. 

    - 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면, 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다. 

- 코딩 테스트에서는 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다. 

 

 

# 풀이

- '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에, 조건의 만족 여부(yes or no)에 따라 탐색 범위를 좁혀서 해결한다. 

- 범위를 좁힐 때는 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀 나간다. 

 

- 중간점의 값은 시간이 지날수록 '최적화된 값'을 찾기 때문에, 과정을 반복하면서 결과값을 중간점 값으로 갱신해준다.

 

 

n, m = map(int, input().split())
data = list(map(int, input().split()))

start, end = 0, max(data)

res = 0
while start <= end:
    total = 0
    mid = (start + end) // 2

    for x in data:
        if x > mid:
            total += x-mid

    if total < m:
        end = mid-1
    else:
        res = mid
        start = mid + 1

print(res)

1. start은 min(data)로 하면 안되는 걸까?

    → 안된다.  min(data)-1도 안되더라...

2. while start < end: 는 안되는 걸까?

    → 안된다. 

 

* 이진탐색에서 start는 안전하게 항상 0으로 가정하자. 

* 반복문으로 구현하는 이진탐색의 while문에서는, start==end 인 상황도 가정한다. 리스트가 하나면 start==end 니까!

 

 

 

* 절단기의 높이는 1부터 10억 까지의 정수 중 하나인데, 이처럼 큰 수를 보면 당연하다는 듯이 가장 먼저 이진 탐색을 떠올려야 한다. 

'Problem Solving' 카테고리의 다른 글

최단 경로 찾기  (1) 2023.12.28
다이나믹 프로그래밍과 메모이제이션  (0) 2023.12.27
파이썬 언어에서, 입력 데이터를 빠르게 입력 받기  (0) 2023.12.26
탐색  (1) 2023.12.26
정렬 기법  (0) 2023.12.25