[백준]2343(파이썬) - 기타레슨

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

2343번: 기타 레슨

 

• 이 문제는 정말 어이없는 실수로 꽤나 시간을 쏟았던 문제입니다.. 해설을 하면서 말씀드리도록 하죠.
• 처음 봤을 때 생각은 '뭔가 기준점이 있어야 하고 그 기준점은 조건에 따라 달라질 수 있다.... 그렇다면 이분 탐색이겠구나'였습니다.
• 이분 탐색에서 가장 핵심은 이분탐색풀이에서의 mid 값을 뭐로 설정하느냐? 라고 저번 이분탐색 포스팅에서 언급한적이 있는데요,
  이번에도 무엇을 mid로 둘 것이냐를 생각하다가 주어진 m 개로 쪼갤 때 사용하는 기준이 되는 합을 mid로 정했습니다.
• 나머지는 일반적인 이분탐색 풀이와 같습니다. 하지만 약간 난이도 있는 이분탐색 문제의 특징처럼 단순히 start와 end 만으로 mid를 찾는 방식이 아니라 주어진 조건을 고려하면서 mid값을 찾아나갔습니다.
• 자세한 설명은 주석에 달아놨으니 참고하시면 될 것 같습니다.
• 추가적으로, 앞으로의 모든 알고리즘 풀이( 새로 푸는 문제, 또는 예전에 풀었던 문제를 리마인드 할 때 ) 주석을 다는 습관을 기르라는 친구의 조언이 있었습니다. 앞으로 주석을 열심히 달아보려고 합니다.

 

( 엇 어이없는 실수를 얘기를 안 했네요. 제가 한 어이없는 실수는 테스트 케이스에서 주어진 m = 3이라는 값을 start 값에 num // 3으로 고정을 시켜서 여러 번 틀린 것입니다.)

 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
data = list(map(int,input().split()))


#순서를 유지해야 하므로 정렬을 사용하면 안된다.
# 이분탐색을 두번 적용 시켜서 
num = sum(data)

start = 0 # num // 3
end = 10000000000
result = num

while start<=end:
    # mid 는 블루레이 크기
    mid = (start+end) // 2 
    if mid < max(data):
        start = mid + 1
        continue
    # cnt 는 블루레이 개수 , tmp 는 블루레이 갱신해주고 있는 블루레이 길이
    cnt,tmp =1,0
    # 하나씩 더하면서 갱신해준다. 
    for i in range(len(data)):
        # 이전 값이랑 지금 값 더해서 mid 보다 작으면 계속 더해준다
        if tmp + data[i] <= mid:
            tmp += data[i]
        # mid 보다 커지면 현재 data[i]가 tmp 로 들어가고
        # 전에 있던 tmp는 0 초기화 해주고 개수 1개 늘려준다.
        else:
            tmp = data[i]
            cnt += 1
    # 개수가 m-1보다 작거나 같으면 이분탐색으로 영상 길이 인 mid값 갱신 로직 실행ㄴ
    if cnt <= m:
        end = mid - 1
        result = min(result,mid)
    else:
        start = mid + 1
print(result)