백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬)
글 작성자: pental
https://www.acmicpc.net/problem/17951
풀이
이분 탐색을 활용해서 시험지 점수 리스트 A를 K개의 그룹으로 나눌 때, 각 그룹의 최소 점수 합 중 최대값을 찾는 문제이다.
문제를 이해하면,
- N개의 시험지 점수가 주어진다.
- 이 점수들은 연속된 그룹으로 K개 이상으로 나눠야한다.
- 그룹의 최소 점수 합이 최대한 커지도록 만든다.
일반적인 풀이로는 시간이 많이 걸리므로, 이분 탐색을 활용해 효율적으로 풀이한다.
- 이분 탐색 대상
- mid 값은 각 그룹의 최소 점수 합 중 최댓값을 의미한다.
- low = 0, high = 20 * 100000 / 시험지 개수 최대값이 10^5이므로, 가능한 최대 점수로 정의한다.
- 이분 탐색 과정
- mid 값을 기준으로 그룹을 나눈다.
- 그룹의 개수가 K이상이면, mid값을 더 크게 설정
- 그룹의 개수가 K미만이면, mid값을 더 작게 설정
코드
# # 백준 17951 - 흩날리는 시험지 속에서 내 평점이 느껴진거야
# 분류 : 이분 탐색
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
low = 0
high = 20 * 100000
answer = -1
while low <= high :
mid = (low + high) // 2
sum = 0
count = 0
for i in range(N) :
sum += A[i]
if sum >= mid :
count += 1
sum = 0
if count >= K :
answer = mid
low = mid + 1
else :
high = mid - 1
print(answer)
'Programming > 백준' 카테고리의 다른 글
백준 17255 - N으로 만들기 (파이썬) (0) | 2025.03.10 |
---|---|
백준 13164 - 행복 유치원 (파이썬) (0) | 2025.03.10 |
백준 2503 - 숫자 야구 (파이썬) (1) | 2025.03.09 |
백준 17944 - 퐁당퐁당 1 (파이썬) (0) | 2025.03.08 |
백준 17952 - 과제는 끝나지 않아! (파이썬) (0) | 2025.03.07 |
댓글
이 글 공유하기
다른 글
-
백준 17255 - N으로 만들기 (파이썬)
백준 17255 - N으로 만들기 (파이썬)
2025.03.10 -
백준 13164 - 행복 유치원 (파이썬)
백준 13164 - 행복 유치원 (파이썬)
2025.03.10 -
백준 2503 - 숫자 야구 (파이썬)
백준 2503 - 숫자 야구 (파이썬)
2025.03.09 -
백준 17944 - 퐁당퐁당 1 (파이썬)
백준 17944 - 퐁당퐁당 1 (파이썬)
2025.03.08