[boj 2343] [Python] 기타 레슨

문제 링크

처음엔 greedy 한 방법으로 시도했다가, 금방 틀렸다는 걸 깨달음. 왜냐하면, 강의의 길이가 정렬된 순서로 주어지지도 않고, 순서를 건드리면 안 되기 때문.

문제 접근 방법을 알기가 어려웠다.

알고 나서도, 이진탐색 문제의 경우 무엇을 탐색 대상으로 놓는지 고민하는 것이 가장 어려운 듯하다.

재귀를 이용해 이진탐색 구현했고, 블루레이 개수 세는 부분은 이진탐색 코드의 원형을 최대한 살려놓기 위해 따로 함수로 뺐다.

# 기타 레슨

import sys
input = sys.stdin.readline

def getBluNo(ar, size):
    blu = [0] * len(ar)
    bluIndex = 0

    for i in ar:
        if blu[bluIndex] + i <= size:
            blu[bluIndex] += i
        else:
            bluIndex += 1
            blu[bluIndex] += i
    return bluIndex + 1     # idx+1
        

def binarySearch(ar, start, end, m):
    if end < start:
        return -1  # fail
    size = (end + start) // 2

    # 블루레이 담기
    no = getBluNo(ar, size)
  
    if no > m:
        return binarySearch(ar, size+1, end, m)
    else:
        global ans
        ans = min(ans, size)
        return binarySearch(ar, start, size-1, m)


n, m = map(int, input().split())
ar = list(map(int, input().split()))
ans = sys.maxsize

binarySearch(ar, max(ar), sum(ar), m)
print(ans)

이 포스트를 마지막으로 당분간 ps는 쉬어야 할 것 같다. 소마 코테 준비도 해야하는데, 3월에 정처기 시험 보고 나서 할 것이다.

3월까지 할일에 대해서는 따로 포스팅 작성하던가 해야겠다.