백준 6236번: 용돈 관리 (S1) 풀이

문제 설명

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

풀이 과정

1. Python 풀이

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

money = [int(input()) for _ in range(N)]

min_k = max(money)
max_k = sum(money)

while min_k <= max_k:
    K = (min_k + max_k) // 2
    cnt = 1
    temp = K
    for i in range(N):
        if temp >= money[i]:
            temp -= money[i]
        else:
            temp = K - money[i]
            cnt += 1

    if cnt <= M:
        max_k = K - 1
        answer = K
    elif cnt > M:
        min_k = K + 1

print(answer)

 
2. Swift 풀이

let input = readLine()!.split(separator: " ")
var n = Int(input[0])!
var m = Int(input[1])!

var money: [Int] = []
for _ in 0..<n {
    money.append(Int(readLine()!)!)
}

var start = money.max()!
var end = money.reduce(0, +)
var answer = 0

while start <= end {
    let mid = (start + end) / 2
    var cnt = 1
    var tempMid = mid
    
    for i in 0..<n {
        if tempMid >= money[i] {
            tempMid -= money[i]
        } else {
            tempMid = mid - money[i]
            cnt += 1
        }
    }
    
    if cnt <= m {
        end = mid - 1
        answer = mid
    } else {
        start = mid + 1
    }
}

print(answer)

 
K의 초기값을 money의 최댓값과 money의 합계를 통해 설정한다는 것과 이분탐색을 통해 'K의 값을' 빠르게 찾아나가는 것이 문제의 키 포인트.
 
문제 이해하는 게 더 어려웠다. 다국어 문제 최악.