BOJ 2343 기타 레슨
4336 단어 2021.02.032021.02.03
https://www.acmicpc.net/problem/2343
시간 2초, 메모리 128MB
input :
- N M(1 ≤ N ≤ 100,000)(1 ≤ M ≤ N)
- 기타 레슨의 길이가 레슨 순서대로 분 단위로(자연수)
output :
- 가능한 블루레이 크기중 최소를 출력
어떤 것을 이분탐색 해야 하는가? 에 대한 것이 떠오르질 않았다.
가능한 블루레이의 최대 길이, 최소한의 길이 범위 사이에서 값을 찾아내야 한다.
mid 로 찾아낸 값에 레슨을 넣으면서 블루레이가 몇 개 만들어지는지 확인.
import sys
n, m = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
lo = max(data)
hi = sum(data)
while lo <= hi:
mid = (lo + hi) // 2
cnt = 0
full = 0
for item in data:
if full + item > mid:
cnt += 1
full = 0
full += item
if full > 0:
cnt += 1
if cnt > m:
lo = mid + 1
else:
hi = mid - 1
print(lo)
while 조건에는 <=이 걸려야 한다.
hi = mid - 1 로 만들기 때문에 우리는 정답보다 -1 된 값을 계속 가지고 있는데 계산이 이루어지다 보면 마지막에 lo = mid + 1의 연산으로 lo가 정답을 가지도록 할 수 있는 것이다.
정렬을 할 수 없는 문제이기 때문에 맨 처음 lo를 초기화 할 때 max(data)를 이용한다.
Author And Source
이 문제에 관하여(BOJ 2343 기타 레슨), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-2343-기타-레슨저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)