기타 레슨 실버 1 (백준, 이진탐색)

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

 

 

import sys

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

ans = 0
s = max(lecture)
e = sum(lecture)
while s <= e:
    mid = (s + e) // 2
    cnt = 0
    temp = 0
  
    for i in lecture:
      if temp+i > mid:
        temp = 0
        cnt+=1
      temp += i
    
    if temp != 0:
      cnt+=1
    
    if cnt > m:
        s = mid + 1
    else:
        e = mid - 1
      
print(s)

최소값을 구하려면 s를 값으로 반환하거나 e에서 mid를 값으로 넣으면 된다. 

일단 시작 값을 나는 1로 설정을 했는데 생각해보면 모든 영상을 블루레이로 담으려고 하는게 길이를 1로 시작한다는 것은 어폐가 있다. 문제를 생각할때 잘 고려해야할 점이라고 생각된다.

 

이 문제에서 시간을 끈 이유 중 하나는 처음에 cnt를 1로 줬는데 어차피 첫 번째에 값이 들어간 이후에 cnt가 증가한다는 생각으로 그렇게 했지만 이후 temp에 남은 값이 있다면 1을 더해주는 부분에서 변수가 발생하여 계속 더 큰 값을 출력했다. 

 

cnt를 0으로 설정하고 시작하는 것이 정석이니 괜한 꼼수를 부리지말자.

 

이진 탐색은 시작과 끝을 합쳐서 나눈 값을 기준으로 하여 문제에서 요구하는 것에 맞게 시작 값과 끝 값을 조정하며 값을 구해야한다.

 

정렬된 리스트에서만 사용가능하다는 것을 잊지말자.