기타레슨
출처 : 백준 #2343
| 시간 제한 | 메모리 제한 |
|---|---|
| 2초 | 128MB |
이전에 참고하면 좋을 문제
문제
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.
강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.
강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.
출력
첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.
입출력 예시
예제 입력 1
9 3
1 2 3 4 5 6 7 8 9
예제 출력 1
17
힌트
강의는 총 9개이고, 블루레이는 총 3개 가지고 있다.
1번 블루레이에 1, 2, 3, 4, 5, 2번 블루레이에 6, 7, 3번 블루레이에 8, 9 를 넣으면 각 블루레이의 크기는 15, 13, 17이 된다. 블루레이의 크기는 모두 같아야 하기 때문에, 블루레이의 크기는 17이 된다. 17보다 더 작은 크기를 가지는 블루레이를 만들 수 없다.
풀이
생각 및 풀이 설명
-
이진 탐색(Binary Search)을 이용하여 해결하였다.
-
start를
max(video), end를sum(video)로 놓았다.- start 이유 : 가장 적은 블루레이의 크기를 가질 때는 배열의 원소 중 가장 큰 값을 넣을 수만 있으면 되기 때문
- end 이유 : 블루레이 개수가 1개일 때는 모든 배열의 원소를 포함해야 하므로 원소의 합으로 정하였다.
-
이진탐색을 돌며 배열의 원소와 temp(한 블루레이 내에 들어갈 원소의 합)를 더한 값이 mid(블루레이의 크기)를 넘어버린다면, 블루레이 개수인
total에 1을 더하여 준다. -
만약 for문을 다 돌았다면, 마지막 블루레이가 남아있으므로 개수에 추가하여 준다.
-
100%에서 틀린 이유 : 처음에는 블루레이의 개수가 원하는 개수 이하일 때 end 값을 업데이트 해줘서 범위를 축소시키고, 원하는 개수와 같다면 해당
mid값과result값을 비교하여 result에 넣어주었는데, 이렇게 해버리면 블루레이에 아무 원소도 들어가지 않는 경우에도 답이 도출 될 수 있는데 그런 경우를 제외해버리는 상황이 발생한다. -
따라서 그냥
if total == m을 제외하고 바로mid와result값 중 최소값을result에 넣어주어야 한다. -
이진탐색에 굉장히 취약했는데, 점점 느낌을 알아가고 있는 중이다. 다른 문제들 처럼 빨리 적응해서 손쉽게 풀어낼 수 있는 날이 왔으면 좋겠다.
python code
# 백준 2343번 기타레슨
from sys import stdin
import copy
import math
input = stdin.readline
n, m = map(int, input().split())
video = list(map(int, input().split()))
start = max(video)
end = sum(video) + 1
result = 10**9 + 1
while start <= end:
mid = (start + end)//2
temp = 0
total = 0
for v in range(len(video)):
if temp + video[v] <= mid:
temp += video[v]
if v == n-1:
total += 1
else:
total += 1
temp = video[v]
if v == n-1 and temp <= mid:
total += 1
# for i in range(len(video)):
# if temp+video[i] > mid:
# total+=1
# temp=0
# temp+=video[i]
# if temp:
# total+=1
if total <= m:
end = mid - 1
# if total == m: ... 이것 때문에 100%에서 틀렸음.. 왜 그런 것일까?
# ... m개를 집어 넣지 못하는 경우에도 정답이 될 수 있나? 그런것같긴 함
# 왜냐하면, 부족한 경우에는 이미 들어간 것을 쪼개면 되기 때문
# 그에 대한 반례가 100%에 들어있었던 것 같음
result = min(mid, result)
else: # 줄여야 함 (total < m)
start = mid + 1
if result < 10**9 + 1:
print(result)
else:
print(max(video))