https://www.acmicpc.net/problem/17951
시간 1초, 메모리 256MB
input :
- N K (1 ≤ K ≤ N ≤ 105)
- 맞은 문제의 개수 x(0 <= x <= 20)
output :
- 최대 점수를 출력
조건 :
- K개의 그룹, 맞은 문제 개수의 합을 구하여 그 중 최솟값을 시험 점수
포인터를 사용해야 하나 싶었는데.. 그렇게 따지기엔 너무 경우의 수가 많은 것 같다.
이분 탐색을 이용해 위치를 잡아야 하나 싶었는데 max 값을 따지기도 뭐하고 그룹의 개수가 어떻게 되는지 모르는 상태에서 할 방법이 아니였다.
그래서 분명 이분탐색이긴 한데 무엇을 해야 하는가가 문제였다.
최대 점수를 target으로 하는 이분탐색이고 그룹의 수를 체크한다면? 답을 구할 수 있겠다.
얻을 수 있는 가장 큰 점수는 모든 맞은 문제를 다 더한 값이므로 high 값을 이와 같이 설정 한다.
그리고 mid 점수를 넘은 경우에만 cnt 를 1개 늘려주고 다시 total을 초기화 하도록 하자.
모든 그룹이 최소 점수를 만족 해야 점수를 얻을 수 있으므로 위와 같은 조건이 발생한다.
import sys
n, k = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
low, high = 0, 0
for item in data:
high += item
while low <= high:
mid = (low + high) // 2
cnt, total = 0, 0
for i in range(len(data)):
total += data[i]
if total >= mid:
cnt += 1
total = 0
if cnt >= k:
low = mid + 1
else:
high = mid - 1
print(high)
