백준-이분탐색(2343 기타레슨)

10 Jul 2020

문제

입력

---

문제 해설

문제를 보자면, 두번째에 주어진 레슨의 길이가 담긴 배열의 각 인덱스별 값(길이)이 끊기지 않게 한 블루레이 안에 들어가야한다. 예를 들면 [1,2,3,4]라는 레슨의 길이가 있다고 하자. 그리고 크기 4의 블루레이가 있으면, [1,2]와 [3], [4]이 각각 크기 4의 블루레이 안에 담겨야 한다. [1,2,3]이 4의 블루레이 안에 들어가있지 못하는 이유는 3을 쪼갤수 없고, 넣으려면 3전체를 넣어야 한다. 그러면 1+2+3 = 6의 크기가 4안에 들어갈 수 없으므로 넣을 수 없다.
문제의 설명은 위와 같다. 그러면 어떻게 풀어야 할까? 포스팅의 제목처럼 이분탐색 을 써야한다. 이분탐색의 하한값과 상한값을 통해서 mid값을 구하고, 길이 배열을 처음부터 돌면서 mid값과 비교하면서 블루레이 갯수를 증가시켜주면 된다. 코드는 다음과 같다. —–

#이 문제는 memorization이 중요
#계속 sum 계산해서 시간초과 났음
#입력값 받는 부분
N, M = list(map(int,input().split()))
lesson_list = list(map(int, input().split()))
#하한값,상한값 셋팅해주기
#두개의 값을 1과 max값으로 세팅해주면 되지만 문제를 통해 아래의 값으로 해도
#된다는 것을 알 수 있다.
left_val = max(lesson_list)-1 #불가능
right_val = sum(lesson_list) #가능

#반복된 계산을 피하기 위한 memorization
plus_sum = [0] * N
#배열의 누적값을 구한다.
for i in range(N):
    if i ==0:
        plus_sum[i] = lesson_list[i]
    else:
        plus_sum[i] = lesson_list[i] + plus_sum[i-1]

#아래 while문 안의 for문에서 인덱스 -1을 처음에 참조하므로
#0을 넣어준다.
plus_sum.append(0)

while True:
    mid = (left_val+right_val)//2
    start_idx = 0
    cnt = 0
    while True:
        #앞에서부터 돌면서 블루레이 갯수 카운트해주기
        for i in range(0, N+1):
            if plus_sum[start_idx+i-1]-plus_sum[start_idx-1] > mid:
                start_idx = start_idx + i - 1
                cnt += 1
                break
            if start_idx + i == N:
                start_idx = start_idx +i
                cnt += 1
                break
        if start_idx >= N:
            break
    #블루레이 갯수가 원하는 갯수보다 클 때
    if cnt > M:
        left_val = mid
    #작을 때
    else:
        right_val = mid
    
    #rigth_val가 유효값이기 때문에, 1차이나면 바로 break
    if right_val - left_val == 1:
        break
    
print(right_val)

사실 위의 풀이가 정답은 아니다. 더 빠른 풀이가 존재한다. 나의 경우에는 2중 while문과 for문으로 예상한것보다 시간이 많이 걸린다. 전형적인 방법으로 더 빠르게 구할 수 있다. 가끔 right_value와 left_value중에 어떤것이 참값인지 해깔릴때 유효/비유효 값을 정해서 반환해주면 안 헷갈리고 좋다. (물론 시간은 조금 더 걸리겠지만)