[알고리즘/이분 탐색] 2343번 : 기타 레슨 - python

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

2343번: 기타 레슨

 

---

• 문제
• 소요시간: 9분 구현(21분 성공)

---

• 설계하기(접근방법) 

1. 입력받기

강의 개수와 블루레이 최소개수

강의 크기를 입력받는다

 

2. 구현하기

정렬된 리스트를 보면 알 수 있는 점이

이분 탐색을 진행해주는 문제다

 

최소값을 max(lec_list)

최대값을 sum(lec_list)로 잡은후

이분 탐색을 진행하여 최소 블루레이 크기를 찾는다

 

3. 출력하기

최소 블루레이를 출력해준다

 

---

• 코드(출력)

total, target = map(int, input().split())
lec_list = list(map(int, input().split()))

start = max(lec_list)
end = sum(lec_list)

while start <= end:
    mid = (start + end) // 2
    cnt = 1
    length = 0
    for i in lec_list:
        if length + i > mid:
            length = 0
            length += i
            cnt += 1
        else:
            length += i
    if cnt > target:
        start = mid + 1
    else:
        end = mid -1


print(start)

---

• 얻어갈 부분

1. start 값을 또 틀려서 디버깅에 10분을 사용했다. 틀렸다면 start, end값을 최우선적으로 조정하고 그 후 cnt나 부등호를 살펴보자