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

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

www.acmicpc.net/problem/17951

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

 

 

 문제

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

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

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

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

 

 입력

 첫 번째 줄에 시험지의 개수 N과 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 ≤ K ≤ N ≤ 105)

 두 번째 줄에 각 시험지마다 맞은 문제의 개수 x가 정수로 주어진다 (0 ≤ x ≤ 20)

 

 출력

 현수가 받을 수 있는 최대 점수를 출력한다.

 

 

 풀이

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int N, K; cin >> N  >> K;
	int arr[100000], s=0;
	for(int i=0;i<N;i++){
		cin >> arr[i];
		s += arr[i];
	}
	
	int pl = 0;
	int pr = s;
	while(pl <= pr){
		int mid = (pl + pr) / 2;
		int sum = 0, cnt = 0;
		for(int k=0;k<N;k++){
			sum += arr[k];
			if(sum >= mid){
				cnt++;
				sum = 0;
			}
		}
		
		if(cnt >= K){
			pl = mid + 1;
		}
		else pr = mid - 1;
	}
	
	cout << pr;
	return 0;
}

 이 문제가 이분 탐색 유형 문제인 것을 알고 풀었는데도 쉽게 접근하지 못했었다. 약간의 참고를 통해 새로운 눈을 뜬 느낌이다. 문제를 읽고 나면 시험지를 나누고 최대 점수를 구하려고 하는 사람들이 많을텐데 이 문제는 최대 점수를 정해놓고 시험지를 나눌수 있는지 없는지를 판단해야 쉽게 풀 수 있다. 이 최대 점수를 정해놓는 과정에서 이분 탐색을 사용할 수 있다. 0에서 모든 시험지의 점수 합까지 이분 탐색을 돌리면서 앞에서부터 더해가면서 정해 놓은 그 값보다 커지면 구간을 나누는 개념으로 구현하여 그 구간의 갯수가 K를 넘으면 만족하기 때문에 pl을 mid+1로 옮겨주면 된다.

 이게 이분 탐색으로 풀리네라는 생각이 드는 문제였다. 좋은 문제로 추천해 줄만하다.