6236번: 용돈 관리

문제 풀이 아이디어

특정 범위에서 하나의 값을 찾는 문제를 연속된 O / X 문제의 개념으로 접근해서 푸는 파라메트릭 서치를 사용하는 문제입니다. 파라메트릭 서치는 이진 탐색을 활용해서 구현하면 됩니다.

파라메트릭 서치를 구현할 때 대부분 이진탐색의 시작과 끝으로 설정할만한 값이 문제에서 주어지지 않는데요. 이 값들을 잘 설정해야 코드의 실행시간을 줄일 수 있을뿐만 아니라 불필요한 예외처리를 줄일 수 있습니다.

이 문제에서 시작 값은 일일소비액 중에 최댓값입니다. 왜냐하면 출금을 했는데 소비를 할 수 없으면 k 값이 될 수 없기 때문입니다. 따라서 k 값은 일일소비액의 최댓값 보다는 커야합니다. 이렇게 하면 k 값이 각각의 일일소비액 보다 작을 때 해야하는 예외처리를 하지 않아도 됩니다.

이진 탐색의 초기 끝 값은 일일소비액을 모두 더한 값으로 설정하면 됩니다. 이 경우 한번의 출금으로 모든 소비를 해결할 수 있으므로 이 보다 큰 k 값은 의미가 없게 됩니다.

코드

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]
var plans = [Int]()
for _ in 0..<N {
    plans.append(Int(readLine()!)!)
}

// k만큼 출력했을 때 생활이 가능한지 확인하는 함수
func isPossible(_ k: Int) -> Bool {
    // 총 출력 횟수
    var cnt = 0
    // 현재 현금 보유액
    var money = 0
    
    // 소비 계획을 순환하면서
    for plan in plans {
        // 현금이 모자라면 출금
        if plan > money {
            cnt += 1
            money = k
        }
        // 당일 소비
        money -= plan
    }
    
    // 출력 횟수가 M 이하면
    return cnt <= M ? true : false
}

// 초기 최솟값은 하루소비액 중에 가장 큰 값
    //👉 출금했는데 소비가 안되면 안되니까
var start = plans.max()!
// 초기 최댓값은 모든 소비액을 합친 값
    //👉 한번 출금해서 모든 소비를 할 수 있으니까
var end = plans.reduce(0, +)

var ans = 0

// 반복문을 통한 파라메트릭 서치 구현
while start <= end {
    let mid = (start + end) / 2
    
    if isPossible(mid) {
        end = mid - 1
        ans = mid
    } else {
        start = mid + 1
    }
}

print(ans)