BOJ - 숫자구슬 2613번 (JAVA)

❓ 문제 - 백준 숫자구슬 2613번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/2613)

2613번: 숫자구슬

 

 

 

📝 문제해결법

1. 문제 해석

• N개의 구슬을 M개의 그룹으로 나눌 떄 그룹의 합 중 최대값이 최소가 되려 한다.
• 이때, 각 그룹의 합의 최대값이 최소가되는 최솟값과, 구슬에서 그룹을 이루는 갯수를 출력하라.

 

2. 해결 방법

• 일단 N이 300이하 자연수, M이 N이하의 자연수이므로 백트래킹이나 조합으로 하기엔 무리가 있어보였고 이런 경우에 이진탐색을 활용해야하는가 생각했지만 Binary Search로 그룹의 최대값의 최솟값의 범위에서 mid(중간값)이 그룹의 최대값일때 몇 개의 그룹으로 나눠지는지 체크하면서 범위를 좁혀간다.
• possible에서 mid가 그룹합의 최대값으로 가정하고 0번 구슬부터 N-1 구슬까지 체크하면서 최대값을 넘지 않는 범위 내에서 그룹을 생성해줄 때 생겨나는 그룹의 수(cnt)를 활용한다.
• 만약 각 그룹의 합 중 최대값인 값(mid)를 가정했을 때 생겨나는 그룹 수가 M보다 크다면 이진탐색의 최소 범위를 mid+1로 , 그룹 수가 M보다 작거나 같다면 이진 탐색의 최대 범위를 mid-1로 줄여준다.
• 그렇게 계속 이진탐색을 돌리면 M개의 그룹으로 구슬을 나눌 때의 그룹의 합의 최대값이 최소값(lower)으로 구해진다.
• 다시 한번 possible 방식으로 그룹의 합의 최대값은 (lower)로 정하고 0번 구슬부터 n-1구슬까지 구슬의 값을 더해주다가 그룹의 합이 lower를 넘으려고 하면 현재까지 카운트한 구슬 수를 출력하고, lower를 넘지 않으면 카운트를 증가시켜준다. 계속 카운트를 하다가 만약 나눠야하는 그룹의 수가 남은 구슬의 수와 같다면 for문을 돌릴 필요없이 현재까지 카운트한(cnt), 1, 1, ... 이런식으로 각 그룹의 갯수를 출력한다.

 

 

3. 삽질 & 느낀점

• 이진탐색까진 구현과정이 떠올랐는데.. mid값을 기준으로 판단근거를 내릴 때 구현을 어떤식으로 해야할지 감이 오지 않았다. 그래서 다른 사람들의 코드를 참고하였고 생각보다 간단하게 0번 구슬부터 n-1구슬까지 sum, cnt를 활용해서 하는 걸 보고 방법을 쭉 보고 다시 나의 코드 방법으로 구현하였더니 통과하였다.
• 그런데 이진탐색에서 국룰 처럼 mid값을 최적의 값으로 쓰이는데 코드들이 다 lower를 최적의 값으로 출력하길래 왜인지 계속 생각했는데 아마 while의 범위가 lower <= mid일 때, 우리가 구하려고 하는 목표 그룹 중 최대합의 최솟값 이기때문이 lower를 기준으로 했구나 이해가 갔다.
• 이진탐색은 범위를 잡는 것보다 어떤 것을 기준으로 선택할지 떠올리기 쉽지가 않다. 관련 문제를 자주 풀어봐야겠다고 느꼈다.

 

💻 소스코드 

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

public class Main {
    public static int n, m;
    public static int[] arr;
    public static int lower, high;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            lower = Math.max(lower, arr[i]);
            high += arr[i];
        }

        // 이분 탐색
        int mid = 0;
        while (lower <= high){
            mid = (lower + high) / 2;
            int cnt = possible(mid);
            if(cnt > m) {
                lower = mid+1;
            } else {
                high = mid-1;
            }
        }
        sb.append(lower).append("\n");

        int cnt = 0;
        int sum = 0;
        for(int i=0;i<n;i++){
            sum += arr[i];
            if(sum > lower){
                m--;
                sum = arr[i];
                sb.append(cnt).append(" ");
                cnt = 1;
            } else {
                cnt++;
            }

            if(m == n-i) break;
        }

        while (m-- > 0){
            sb.append(cnt).append(" ");
            cnt = 1;
        }
        System.out.println(sb.toString());
    }


    // 갯수 카운팅
    public static int possible(int mid){
        int sum = 0;
        int cnt = 1;
        for(int i=0;i<n;i++){
            sum += arr[i];
            if(sum > mid){
                cnt++;
                sum = arr[i];
            }
        }
        return cnt;
    }

}