[이분탐색] - S1_2343_기타레슨

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

2343번: 기타 레슨

 

📌 - 처음 생각한 풀이

1. 입력을 받을 때 전체의 합을 더해서, 0~전체의 합의 중간 값을 mid로 사용
2. start가 end보다 크거나 같아질 때 까지 반복
3. for문을 돌면서 lay의 값을 증가시켜서 해당하는 갯수가 M보다 큰지 작은 확인
4. M보다 크면 start를 증가시켜서, lay의 갯수를 줄이도록 함
5. M보다 작거나 같으면 end를 감소시켜서 lay의 갯수를 맞춤
6. start의 값을 출력

 

- 이렇게 풀이를 하면 맞다고 생각해서 제출을 했는데 틀려서, 다른 테스트 코드

5 4
1 2 3 4 5

로 테스트를 해보니 결과값이 3으로 출력

실제 답은 5

 

mid값보다 더 큰 값을 담으려고 할 때 체크를 안해주고 있었다.

 

아래에 해당하는 코드

  if (start < arr[i]) {
                start = arr[i];
            }

 

로 최소값을 입력 받는 값의 최대값으로 지정해주니까 정답처리가 됨

🔥 - Java 코드

 

package 추가문제.S1_2343_기타레슨;

import java.io.*;
import java.util.*;

public class Main {
        public static int N,M,result=Integer.MAX_VALUE;
        public static int[] arr;

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        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());

        int start =0;
        int end = 0;
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            end += arr[i];
            if (start < arr[i]) {
                start = arr[i];
            }
        }

        while(start<=end){
            int mid = (start+end)/2;
            int lay = 1;
            int ans = 0;
            for(int i=0;i<N;i++) {
                if(ans + arr[i] > mid){
                    lay++;
                    ans = 0;
                }
                ans += arr[i];
            }

            if(lay > M ){
                start = mid+1;

            }else{
                end = mid-1;
            }

        }

        System.out.println(start);


    }

}