[백준]2512번 예산

단순한 이분탐색 문제다.

 

1.문제된 부분

문제가 된 부분은 값을 찾은 후에도 조건문이 한번 더 도는 경우 정답에서 1~2정도 차이나는 것이었다.

조건식도 계속 바꿔보고 했는데, 절대 모든 반례를 만족하지는 못했다.

 

한시간정도 고민하다가 결국 다른 사람들이 푼 코드를 봤는데

1.조건문 안에 정답 값을 미리 저장하거나

2.max를 출력하면 되더라.

 

mid에 꽂혀서 mid값이 정답으로 나오게 하려고 난리쳤는데 그냥 max를 출력해주면 됐던 것이다....

답을 알고나면 너무도 간단한 문제였는데, 계속 mid값에 집착해서 까막눈으로 풀었던 문제

 

2.코드

import Foundation

let N = Int(readLine()!)
let budgets = readLine()!.split(separator: " ").map{ Int(String($0))!}
let M = Int(readLine()!)!

var min = 0; var max = budgets.max()!
var ans:Int

while(min<=max){
    var count = 0
    let mid = (min+max)/2

    for budget in budgets {
        if budget<=mid{
            count += budget
        }
        else{
            count += mid
        }
    }
    
    if count<=M{
        ans = min
        min = mid+1
    }
    else{
        max = mid-1
    }

}

print(max)