본문 바로가기
Algorithm/백준풀이

[알고리즘 문제풀이] 백준 2613 숫자구슬 (JAVA코드)

by 계범 2022. 3. 16.

목차

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

     

    2613번: 숫자구슬

    첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100

    www.acmicpc.net

    import java.util.*;
    import java.io.*;
    
    /**
     * 1. 이분탐색으로 최대값의 크기를 지정
     * 
     * 2. 그에 따른 그룹으로 나누기(각 그룹별 개수 체크)
     * 
     * 3. 최대값이 최소가 될 때 출력
     */
    
    public class 숫자구슬 {
    
        public static int n,m, result;
        public static int[] groupList, beads;
        public static void main(String[] args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
            String[] strs = br.readLine().split(" ");
            n = Integer.parseInt(strs[0]);
            m = Integer.parseInt(strs[1]);
    
            beads = new int[n];
            strs = br.readLine().split(" ");
            for(int i = 0; i < n; i++){
                beads[i] = Integer.parseInt(strs[i]);
            }
    
            groupList = new int[m];
    
            binarySearch();
            groupCheck();
            bw.write(result +"\n");
    
            for(int i = 0; i < m; i++){
                bw.write(groupList[i] + " ");
            }
    
            bw.flush();
            bw.close();
        }
    	
        // 그룹 개수 맞추기(0 개수 그룹 없애기)
        public static void groupCheck(){
            int idx = 0;
            for(int i = 0; i < m; i++){
                if(groupList[i] == 0){
                    idx = i-1;
                    groupList[i]++;
                    while(true){
                        if(groupList[idx] != 1){
                            break;
                        }
                        idx--;
                    }
                    groupList[idx]--;
                }
            }
        }
    
        public static void binarySearch(){
            int start = 1;
            int end = 100*n;
            
            while(start <= end){
                int mid = (start+end)/2; // 최대값
    
                if(isPossible(mid)){
                    end = mid-1;
                    result = mid;
                }else{
                    start = mid+1;
                }
            }
        }
    
        public static boolean isPossible(int mid){
            int groupSum = 0; // 현재 그룹의 합
            int groupIdx = 0; // 그룹 idx
    
            int[] groupNum = new int[m]; // 그룹별 개수
    
            for(int i = 0; i < n; i++){
                if(mid < beads[i]){ // 현재 지정된 최대값보다 구슬숫자가 더 크면 false
                    return false;
                }
                // 현재 그룹에 더해도 최대값이 안넘으면 더하기
                if(groupSum + beads[i] <= mid){
                    groupSum += beads[i];
                }else{
                    groupSum = beads[i];
                    groupIdx++;
                }
                if(groupIdx == m){
                    return false;
                }
                groupNum[groupIdx]++;
            }
    
            groupList = groupNum;
            return true;
        }
    }

    댓글