[파이썬 알고리즘 문제풀이 입문] 이분탐색(결정알고리즘) & 그리디 알고리즘 - 뮤직비디오

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 대에는 라이브에서의 순서가 그대로 유지되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def Count(mid):
    sum = 0
    count = 1
    for i in mins:
        if (sum+i) > mid:
            count += 1
            sum = i
        else:
            sum += i
    return count

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

lt = 1
rt = sum(mins)
largest = max(mins)
res = 0

while lt <= rt:
    mid = (lt+rt)//2
    if mid >= largest and Count(mid) > M:
        lt = mid + 1
    else:
        res = mid
        rt = mid - 1

print(res)

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val (N, M) = readLine().split(" ").map { it.toInt() }
    val mins = readLine().split(" ").map {it.toInt()}

    var lt = 1
    var rt = mins.sum()
    var largest = mins.max()
    var mid = 0
    var res = 0

    while(lt<=rt) {
        mid = (lt+rt)/2
        if(mid >= largest && Count(mid, mins) >= M) {
            lt = mid + 1
        } else {
            res = mid
            rt = mid - 1
        }
    }
    println(res)
}

fun Count(mid : Int, mins : List<Int>) : Int {
    var count = 0
    var sum = 0
    for(i in mins) {
        if(sum+i > mid) {
            count += 1
            sum = i
        } else {
            sum += i
        }
    }
    return count
}

- 이전 문제와 동일한 방법(이분탐색 사용 / 결정 알고리즘)으로 구하는 문제이다.

- 한 가지 주의해야 하는 점은, mid의 값이 입력받은 값들 중 최댓값 보다 크거나 같아야 한다는 조건이 추가되어야 한다.