백준 2343 파이썬 코드 답안

문제

강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 레슨 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 레슨의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 레슨의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 레슨의 길이가 레슨 순서대로 분 단위로(자연수)로 주어진다. 각 레슨의 길이는 10,000분을 넘지 않는다.

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

힌트

레슨은 총 9개이고, 블루레이는 총 3개 가지고 있다.

1번 블루레이에 1, 2, 3, 4, 5, 2번 블루레이에 6, 7, 3번 블루레이에 8, 9 를 넣으면 각 블루레이의 길이는 15, 13, 17이 된다. 블루레이의 길이는 모두 같아야 하기 때문에, 블루레이의 길이는 17이 된다. 17보다 더 작은 길이를 가지는 블루레이를 만들 수 없다. 

 

문제풀이

처음에 전체적인 접근 방법은 전체 기타레슨 시간의 평균값부터 하나씩 올려가며 살펴보는 식으로 살펴봤다. 예를 들어, 위의 예시의 평균은 15이다. 15분씩 시간을 나눈다고 했을 때, 3개로 나누어지는지 확인한다. 만약에 안 나누어지면 시간을 16으로 설정하고 다시 똑같은 것으로 확인하는 방식으로 접근을 했다. 처음 이렇게 구현해서 제출했을 때는 50%까지 진행된 후, 시간 초과가 발생했다. 즉, 테스트 케이스에 따라 시간이 너무 많이 오버될 가능성이 있는 것이다.

나는 여기서 레슨을 나누는 방식은 문제가 없다는 것으로 가정했다. 왜냐하면 레슨의 길이가 10,000분이고 레슨의 수가 100,000이기 때문에 1,000,000,000분에 대한 샘플링을 다 진행을 해야했기 때문이다. 만약 값이 15부터 시작해서 20쯤에 있으면 문제가 없을텐데, 15부터 시작해서 999,999,999분이 답이라면 반드시 시간 초과가 날 수 밖에 없기 때문이다.

여기서 나는 이분 탐색을 통해서 레슨 시간의 평균 값을 필터링 하기로 결정했다. 처음부터(Index 0) 마지막의 앞(index -2)까지 살펴보고, 거기에 따라 마지막을 함께 살펴본다. 여기까지 살펴봤을 때, 레슨을 m등분보다 더 많이 나눠야 한다면 레슨 시간이 불충분하다고 판단한다. (m=4, 평균시간 15분일 때, 5등분 되었다는 것은 더 많은 시간이 필요하다는 소리). 따라서 left index의 값을 올려주었다. 

반면 레슨 시간이 m등분보다 적게 나누어 진다는 것이 확인되면, 지금 가지고 있는 평균 레슨 시간을 통해서 값을 구할 수 있다는 것으로 판단한다. 예를 들어 1 1 1 1 1 1 1 1 10을 3등분한다고 가정하면, 내가 짠 판별 기준으로는 9까지 한 덩어리로 모두 더해져 버린다. 즉, 9와 10으로 나누어지게 되어 2등분이 된다. 나는 이 2등분, 정확하게 말하면 앞에 있는 1등분이 반드시 더 잘게 쪼개질 수 있다고 판단하여 m등분보다 적게 나누어진다는 것이 확인되면, 답의 가능성이 있기 때문에 답으로 체크했다. 

위의 가정을 반복해서 left_idx가 right_idx보다 커지는 순간 이분 탐색을 종료하도록 했다.

import sys

n,m = map(int,sys.stdin.readline().split())
my_list = list(map(int,sys.stdin.readline().split()))

answer = 9876543210 #무슨 수가 올지 모르니 가장 큰 수
left_cnt = max(my_list) #살펴볼 왼쪽 값은 가장 큰 값보다 크거나 같아야 한다. 1,1,1,1,10의 경우 10보다 작은 수는 살펴볼 필요가 없다.
right_cnt = n * 10000 # n개의 갯수에 각 레슨당 10,000분이 최대치이니 그 값을 곱해준다.
mid_cnt = (left_cnt + right_cnt)//2 #mid_cnt는 살펴볼시간이다.
while left_cnt <= right_cnt :
    temp_sum = 0
    slit_cnt = m
    for i in range(len(my_list)-1) : #바로 앞까지 살펴본다.
        if temp_sum + my_list[i] <= mid_cnt:
            temp_sum += my_list[i]
        else :
            temp_sum = my_list[i]
            slit_cnt -=1

    if temp_sum + my_list[-1] <= mid_cnt : #만약 마지막의 temp_sum에 마지막 값을 더했을 때, mid_cnt보다 작으면 한 셋트가 될 수 있으니 cnt하나 줄여준다
        slit_cnt -=1
    else :
        if my_list[-1] <= mid_cnt : #아닌 경우에는 최소 2개가 빠진다고 볼 수 있음.
            slit_cnt -=2


    #답이 될 수 있는지 가능성을 확인하는 곳이다. 
    #만약 cnt가 m보다 적게 나누어졌다는 것은 언제든지 더 분할될 수 있다는 소리다.
    if slit_cnt >= 0 :
        right_cnt = mid_cnt-1
        if answer > mid_cnt :
            answer = mid_cnt
    #만약 cnt가 m보다 더 많이 나누어졌다는 것은 시간이 부족하다는 소리다.
    elif slit_cnt < 0 :
        left_cnt = mid_cnt +1
    mid_cnt = (left_cnt + right_cnt) // 2


print(answer)