문제
넓은 시험 범위와 어려운 과제로 유명한 '운영체제로 보는 데이터베이스시스템 알고리즘' 수업은 시험지가 너무 많아 실내에서는 시험을 치를 수 없어서 야외에서 시험을 진행한다. 해당 수업의 수강생인 현수는 오랜 시간에 걸쳐 풀 수 있는 모든 문제를 풀었고 제출만을 남겨두고 있었다. 그러나 갑자기 불어오는 강풍에 현수의 시험지가 모두 날아가 버렸고, 날아간 시험지를 줍는 동안 남은 시간을 다 써버리고 말았다.
시험지에 명시된 규칙 중에는 채점하는 조교의 편의를 위해 시험지를 반드시 순서대로 제출하라는 규칙이 있는데, 이 규칙 때문에 현수는 힘들게 치른 시험이 0점 처리될 위기에 빠지게 되었다!
그러나, 마음씨 좋은 조교인 주찬이는 평소 수업에 열심히 참여한 현수에게 한 번의 기회를 주기로 했다. 규칙은 규칙이므로 많은 점수를 줄 수는 없고, 시험지를 현재 순서 그대로 K개의 그룹으로 나눈 뒤 각각의 그룹에서 맞은 문제 개수의 합을 구하여 그 중 최솟값을 시험 점수로 하기로 하였다. 현수가 이번 시험에서 받을 수 있는 최대 점수를 계산하는 프로그램을 작성하자.
현수는 모르는 문제를 아예 풀지 않기 때문에 현수가 푼 문제는 모두 맞았다고 생각할 수 있으며, 조교는 마음씨가 좋아서 자신이 줄 수 있는 최대한의 점수를 준다.
입력
첫 번째 줄에 시험지의 개수 N과 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 ≤ K ≤ N ≤ 105)
두 번째 줄에 각 시험지마다 맞은 문제의 개수 x가 정수로 주어진다 (0 ≤ x ≤ 20)
출력
현수가 받을 수 있는 최대 점수를 출력한다.
코드
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
test = list(map(int, input().split()))
acc = [0] # 누적합
for i in range(n):
acc.append(acc[i]+test[i])
def possible(mid):
cnt = 0
prev = 0
for i in range(len(acc)):
if (acc[i] - acc[prev]) >= mid:
prev = i
cnt += 1
if cnt >= k:
return True
else:
return False
# 현수가 받을 수 있는 최대의 점수 구하기
start, end = 0, 20 * int(1e5)
ans = 0
while start <= end:
mid = (start + end) // 2
if possible(mid):
ans = mid
start = mid + 1
else:
end = mid - 1
print(ans)
현수가 받을 수 있는 최대의 점수를 매개 변수 탐색을 통해 구한다. start와 end 초기값은 문제에서 답으로 나올 수 있는 최솟값, 최댓값인 0, 2000000으로 설정하고 매개 변수 탐색을 한다. possible 함수는 시험지들을 각 그룹으로 나눴을 때 그룹별 맞춘 문제의 합이 mid 이상인지 판단하는 함수이다. 리턴값이 True라면 현재 mid 값보다 큰 점수를 받을 수 있는지 알아보기 위해 start값을 mid + 1로 갱신해주고 그렇지 않다면 end값을 mid - 1로 갱신하여 최댓값을 찾는다.
매개 변수 탐색은 이분탐색과 비슷하지만 target값을 찾는 것이 목표인 이분탐색과 다르게 조건에 맞는 최솟값 또는 최댓값을 찾는 알고리즘이다. 현수가 받을 수 있는 점수의 최댓값을 찾는 이 문제에서는 매개 변수 탐색을 이용하여야 한다.
'문제풀이 > 이분탐색' 카테고리의 다른 글
[Python/파이썬] 백준 18113번 그르다 김가놈 (0) | 2023.07.19 |
---|---|
[Python/파이썬] 백준 18114번 블랙 프라이데이 (0) | 2023.07.05 |
[Python/파이썬] 백준 1939번 중량제한 (0) | 2023.06.28 |
[Python/파이썬] 백준 2118번 두 개의 탑 (0) | 2023.06.08 |
[Python/파이썬] 백준 1477번 휴게소 세우기 (0) | 2023.05.03 |