[매개변수탐색][백준 17951] 흩날리는 시험지 속에서 내 평점이 느껴진거야

 

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

문제

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

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

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

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

입력

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

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

출력

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

 

풀이

처음 해당 문제를 풀 때, 그룹을 나눌 때 연속적인 값이 아니라고 생각을 했다. 문제를 제대로 읽자!

1. 브루트포스로 접근하면 범위가 커서 엄청나게 시간을 초과하게 된다. 

 

2. 매개변수 탐색 

2-1) 왜 매개변수탐색으로 문제를 풀까 

• 최대화, 최소화 문제, 탐색의 기준을 정하고 최적의 값을 찾는다. 
• 값이 범위가 크고, 특정 값에 따라 만족 여부를 판변 가능.
  • 즉 최종합을 최소 특정값이라고 할 때 몇 개의 그룹으로 만들 수 있을지 판별할 수 있다. 

 

2-2) 매개변수 탐색 과정 

K 그룹의 합이 최소가 X인 값을 찾아야 한다. 

>> 그룹 합이 X 이상이고 그룹이 M개를 만족애햐 한다. 이 때의 X의 최솟값을 구해야 한다. 

>> X 최솟값은 lower bound를 이용해 구하자 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int e = 0;
        int s = 0;
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            e += arr[i];
        }

        // 그룹의 합이 x 이상이 되고 그룹이 k개인 i를 찾는 바이너리 서치
        // 연속 합이 x 이상.
        // 그룹의 개수는 k 개
        int val = 0;
        while (s <= e) {
            int mid = (s + e) / 2;
            val = 0;    // K 그룹의 각 합을 계산
            int group = 0;
            for (int i = 0; i < N; i++) {
                val += arr[i];
                if(val >= mid) {
                    group++;
                    val = 0;
                }
            }

            if (group >= K) {
                // group 감소시켜서 K가 되어야 함 -> mid 증가시켜야 함 -> s 증가
                s = mid + 1;
            } else {
                // group 증가 시켜서 K가 되어야 함 -> mid 감소 -> e 감소
                e = mid - 1;
            }
        }
        System.out.println(e);
    }
}