(Python/파이썬) - 백준(BOJ) 17951번 : 흩날리는 시험지 속 내 평점이 느껴진거야

https://www.acmicpc.net/problem/17951

17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야

---

• 문제 : 

넓은 시험 범위와 어려운 과제로 유명한 '운영체제로 보는 데이터베이스시스템 알고리즘' 수업은 시험지가 너무 많아 실내에서는 시험을 치를 수 없어서 야외에서 시험을 진행한다. 해당 수업의 수강생인 현수는 오랜 시간에 걸쳐 풀 수 있는 모든 문제를 풀었고 제출만을 남겨두고 있었다. 그러나 갑자기 불어오는 강풍에 현수의 시험지가 모두 날아가 버렸고, 날아간 시험지를 줍는 동안 남은 시간을 다 써버리고 말았다.

 

시험지에 명시된 규칙 중에는 채점하는 조교의 편의를 위해 시험지를 반드시 순서대로 제출하라는 규칙이 있는데, 이 규칙 때문에 현수는 힘들게 치른 시험이 0점 처리될 위기에 빠지게 되었다!

 

그러나, 마음씨 좋은 조교인 주찬이는 평소 수업에 열심히 참여한 현수에게 한 번의 기회를 주기로 했다. 규칙은 규칙이므로 많은 점수를 줄 수는 없고, 시험지를 현재 순서 그대로 K개의 그룹으로 나눈 뒤 각각의 그룹에서 맞은 문제 개수의 합을 구하여 그 중 최솟값을 시험 점수로 하기로 하였다. 현수가 이번 시험에서 받을 수 있는 최대 점수를 계산하는 프로그램을 작성하자.

 

현수는 모르는 문제를 아예 풀지 않기 때문에 현수가 푼 문제는 모두 맞았다고 생각할 수 있으며, 조교는 마음씨가 좋아서 자신이 줄 수 있는 최대한의 점수를 준다.

 

 

 

---

• 풀이 :

이분탐색 문제였습니다.

 

이분탐색의 파라매터를 "각 그룹에서 받을 수 있는 최댓값" 으로 하여 0부터 최고점수인 2,000,001 사이 값 각각마다 총 몇 개의 그룹으로 나누는지 체크합니다. 

 

풀이입니다.

 

1.  left는 0, right는 해당 시험에서 받을 수 있는 최고점수인 2,000,001로 설정합니다.

 

2. mid값은 해당 시험에서 각 그룹이 받을 수 있는 최고점수이며 이 값이 넘어가면 그룹을 하나 나누어야 한다는 뜻입니다.

 

3. 점수들의 배열인 nums에서 앞에서부터 더해가며 mid값을 넘었을 때, 그룹을 하나 나눠줍니다.

 

4. 점수들에 대해 1회 그룹을 나누는 계산이 끝난 후, 나눈 그룹과 K를 비교하여 left와 right의 범위를 조절해줍니다.

 

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

N,K = map(int,input().split())
nums = list(map(int,input().split()))

left, right = 0, 10**5 * 20 + 1
answer = 0
while left <= right:
    mid = (left + right)//2
    total_score, divided_group = 0, 0 # 현재 그룹의 시험점수 총합, 그룹의 개수

    for i in nums: # 시험지의 순서가 있으므로 선형탐색으로 접근
        if total_score + i >= mid:  # 현재까지 더한 시험지의 점수가 최소값의 후보인 mid를 넘었을 경우 그룹을 나눠야 하므로 그룹 개수를 +1 현재 그룹의 총합을 0으로 초기화
            total_score = 0
            divided_group += 1
        else:
            total_score += i

    if divided_group < K: # K 개보다 적은 그룹인 경우 최솟값의 범위를 증가시켜야함
        right = mid - 1
    elif divided_group == K: # K개인 경우 정답 후보
        answer = max(mid,answer)
        left = mid + 1
    else: # K개보다 많은 경우 최솟값의 범위를 감소시켜야함
        left = mid + 1
print(answer)