백준 2512번: 예산

엄기훈·2022년 5월 22일

매개 변수 탐색 백준 알고리즘 이진 탐색

알고리즘 풀이

목록 보기

4/9

❓ 문제

2512번: 예산

처음 풀어보는 유형의 문제였다. 매개 변수 탐색을 완벽하게 이해하고 있다면 간단히 풀 수 있는 문제! 대신 반례를 보면서 조건들을 잘 찾아 나가야 한다.

⌨️ 전체 코드

package main

import (
	"fmt"
	"sort"
)

func main() {
	N := 0
	need := []int{}
	M := 0

	fmt.Scan(&N)

	sum := 0
	for i := 0; i < N; i++ {
		input := 0
		fmt.Scan(&input)
		sum += input
		need = append(need, input)
	}
	fmt.Scan(&M)

	sort.Ints(need)
	if sum <= M {
		fmt.Println(need[N-1])
		return
	}

	start := 0
	end := need[N-1]
	for start + 1 < end {
		mid := (start + end) / 2

		sum := 0
		for _, v := range need {
			if v >= mid {
				sum += mid
			} else {
				sum += v
			}
		}

		if sum > M {
			end = mid
		} else {
			start = mid
		}
	}
	fmt.Println(start)
}

💡 풀이

요청한 금액의 총합이 예산보다 적으면 그냥 요청한 금액의 최대값을 출력한다.
그렇지 않으면 매개 변수 탐색을 통해 상한액을 구해야 한다.
1. 상한액의 구간은 1~(요청한 금액의 최대값)이다.
  - 왜냐하면 예산의 최소금액이 지방의 개수 N이라 각 지방은 적어도 1의 예산은 받을 수 있다.
2. 즉, 초기의 start 값은 0, end는 요청 금액의 최대값이다.
3. 요청한 금액의 리스트를 돌면서 요청한 금액이 상한액 mid를 넘으면 총합에 상한액을 더하고 그렇지 않으면 원래의 값을 더한다.
4. 요청한 금액의 총합이 예산보다 넘으면 end는 mid가 되고 그렇지 않으면 start는 mid가 된다.
5. 다시 mid를 구하면서 start + 1 < end 가 아니게 되는 순간의 start가 답이다.

🔁 삽질

상한액의 구간의 최소값을 처음에는 요청 금액의 최소값으로 선정했는데 생각해보니 예산이 최소값 보다도 작을 수 있다는 걸 간과했다. 상한액의 최소값은 1이어야 한다.
이진 탐색을 할 때의 while문의 조건을 어떻게 선정해야 하는지 헷갈렸다.
매개 변수 탐색을 마친 후 정확히 어떤 값이 정답인지 헷갈렸다.