2343번: 기타 레슨
강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
이분탐색으로 문제를 해결할 수 있다.
이분탐색을 진행하면서 중간값(mid)이 블루레이 최소 크기의 후보가 된다.
각 레슨의 길이가 저장된 배열을 차례대로 탐색하여 한 블루레이당 레슨 길이의 합이 mid보다 작도록 레슨을 그룹으로 분리한다.
예를 들어, mid = 15 이고, 레슨의 길이가 차례대로 1 2 3 4 5 6 7 8 9 이면, 한 블루레이당 레슨 길이의 합이 mid보다 작도록 나누면 (1,2,3,4), (5,6), (7), (8), (9) 로 나눌 수 있다.
각각의 블루레이 레슨의 길이의 합은 10, 11, 7, 8, 9가 되어 mid인 15를 넘지 않는다.
- 만약 이렇게 레슨을 분리한 그룹의 수가 M보다 크다면(즉, 총 필요한 블루레이 개수가 M보다 크다면)
left = mid + 1 로 변경하고,
- 레슨을 분리한 그룹의 수가 M보다 작거나 같다면 right = mid - 1로 변경해준다.
소스코드 :
'BOJ' 카테고리의 다른 글
| [백준 2660번] 회장뽑기 (java) (0) | 2021.03.02 |
|---|---|
| [백준 4358번] 생태학 (java) (0) | 2021.03.02 |
| [백준 6236번] 용돈 관리 (java) (0) | 2021.03.01 |
| [백준 5052번] 전화번호 목록 (java) (0) | 2021.02.27 |
| [백준 2056번] 작업 (java) (0) | 2021.02.26 |