Java 백준 문제풀이 (56) 2343_ 기타 레슨

예전에 풀었던 문제인데 그래프/트리 외에 탐색 문제를 풀어본 경험이 없어서 그런지 해결 방법을 도출하는 것부터 너무 어려웠었다.

근래 풀어본 모든 문제들 중 가장 어려웠음..

 

다시 생각해봐도 쉽게 풀 자신이 없어서 다시 한 번 풀어보기로 했다.

이번엔 내가 어려웠던 문제라서 좀 더 자세하게 적을 예정이다.

 

늘 그렇듯 문제 조건을 바탕으로 해결 방법을 도출해보자.

 

 

 
        // 강의의 순서가 바뀌면 안된다.
        // 블루레이 개수는 최소 - 모든 블루레이 개수는 같아야 한다.
        // => 최소 블루레이의 크기는 가장 용량이 큰 강의와 같다.
        // => 최대 블루레이 크기는 모든 강의 용량의 합과 같다.
 
        // 강의 수 최대 100,000
        // n^2의 복잡도가 필요한 연산 사용 시 1,000,000,000
        // 제한시간 2초이므로 제일 넉넉한 기준인 초당 10억회 연산으로도 부족함
        // O(nlogn) => 500000
        // nlogn의 이진 탐색을 수행하자.
 

 

강의를 모두 같은 크기의 블루레이에 넣어야한다. 그런데 강의 순서는 바뀌면 안된단다.

이 문장에 낚이는 순간 머리 속에서 이진 탐색은 지워지고 (이진탐색은 정렬이 필수이므로) 도저히 헤어나올 수 없는 구멍에 갇힌다.

 

근데 문제에서 제시하는 조건을 보면, 블루레이는 모두 같은 크기의 블루레이를 사용해야 한다.

강의 용량이 9 1 1 1 이더라도 최소한 9라는 용량의 블루레이가 필요한 것이다.

반대로 블루레이가 한 개 주어진다고 생각했을 때 블루레이의 최대 크기는 강의 총 합과 같다.

 

강의 수가 최대 100,000이기 때문에 n^n으로 탐색할 수는 없다.

그리고 탐색 알고리즘은 정렬과 달리 선택지가 많지도 않은데 이 상황에서 시도할 수 있는 건 이진 탐색과 그리디 탐색 정도 뿐일 것이다.

근데 난 그리디 알고리즘 문제 풀어본 경험이 없어서 잘 모름 ㅎㅎ

따라서 이진탐색으로 선택지가 좁혀졌다.

 

이제 또 야매 수도코드 시간이다.

 

 

 

public class Main {
    public static void main(String[] args) {
        // 강의의 순서가 바뀌면 안된다.
        // 블루레이 개수는 최소 - 모든 블루레이 개수는 같아야 한다.
        // => 최소 블루레이의 크기는 가장 용량이 큰 강의와 같다.
        // => 최대 블루레이 크기는 모든 강의 용량의 합과 같다.
 
        // 강의 수 최대 100,000
        // n^2의 복잡도가 필요한 연산 사용 시 1,000,000,000
        // 제한시간 2초이므로 제일 넉넉한 기준인 초당 10억회 연산으로도 부족함
        // O(nlogn) => 500000
        // nlogn은 내가 아는 건 이진 탐색 뿐이다.
 
        // 레슨 수 N, 블루레이 개수 M 입력 받기
        // 강의 배열 입력 arr
 
        // 제일 큰 용량의 강의 저장 변수 max
        // 모든 강의 용량 저장 변수 sum
 
        // N만큼 반복하며 N 크기의 배열에 강의 길이 입력 받기
        // lecture[i] = arr
        // max = Math.max(max, arr[i])
        // sum = arr[i-1] + arr[i]
 
        // 이진탐색(강의 배열, 최대값, 누적합, 블루레이 개수)
    }
 
    // 이진탐색 (강의 배열, 최대값, 누적합, 블루레이 개수)
    // 최소값 = 최대값
    // 최대값 = 누적합
    //
    // 반복문 ( 최소값이 최대값보다 작거나 같은 동안 )
    // 중간값 = (최소값+최대값) / 2
    // 카운트 = 0;
    // 합계 = 0;
    //
    // 반복문 (강의 배열 길이만큼) {
    // i 부터 더하자
    // 만약 합계가 중간값과 같거나 크다면?
    // 카운트 증가
    // 합계 초기화
    //
    // 만약 합계가 0이 아니라면?
    // 카운트 증가
    //
    // 만약 카운트가 블루레이 개수보다 작거나 같다면?
    // 최대값 = 중간값-1
    //
    // 만약 카운트가 블루레이 개수보다 크다면?
    // 최소값 = 중간값+1
 
    // 탐색이 모두 끝나면 출력
}

 

근데 지금 문제 풀면서 실시간으로 글 작성하고 있어서 위 주석대로 풀어서 맞을지 나도 모른다.

아마 한 번은 또 고쳐야할 듯하지만 세세한 부분을 제외하면 거의 확실하니 위 주석을 토대로 설명해보겠다.

 

우선 첫 번째로 아까 말했듯이 블루레이 크기위 최소값 (최대 용량의 레슨 크기)와 최대값 (누적합)을 구해야 한다.

 

다 구했으면 이진 탐색으로 들어간다.

 

최소값, 최대값, 중간값 구하는 건 이진탐색의 기본이니 다들 알고 있을 것이다.

이후 과정이 추가되는데, 강의를 0번부터 더하면서 중간값이 될 때마다 카운트를 올리고 합계를 초기화한다.

그리고 반복문이 끝났는데 합계가 0이 아니라면 카운트를 1 증가시킨다.

 

예를 들어 누적합이 20이고 중간값이 10인데 배열의 합이 10에서 카운트, 다시 10에서 카운트, 그리고 2가 남았다면 20인 강의 영상을 10 크기의 블루레이에 저장할 경우 실제 블루레이 cd는 세 장 필요한 것이다. 

 

우리는 원하는 블루레이 개수를 미리 문제에서 지정해주기 때문에

이진 탐색의 작동 방식대로 조건에 맞지 않으면 최소값이나 최대값을 계속해서 움직이며 최적의 값 (해당 블루레이 개수를 만족하면서도 가장 작은 값)을 찾아내면 된다.

 

.

 

그리고 지금 다 풀어보고 왔는데 역시나 조금 틀렸다.

그래도 기본 흐름은 거의 같음.

 

힌트 1. 어느 시점에 더해야하는지 다시 한 번 생각할 것

힌트 2. 정답을 어디서 누가 출력하는지 다시 한 번 생각할 것

 

풀어보삼

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main {
    public static void main(String[] args) throws IOException {
        // 강의의 순서가 바뀌면 안된다.
        // 블루레이 개수는 최소 - 모든 블루레이 개수는 같아야 한다.
        // => 최소 블루레이의 크기는 가장 용량이 큰 강의와 같다.
        // => 최대 블루레이 크기는 모든 강의 용량의 합과 같다.
 
        // 강의 수 최대 100,000
        // n^2의 복잡도가 필요한 연산 사용 시 1,000,000,000
        // 제한시간 2초이므로 제일 넉넉한 기준인 초당 10억회 연산으로도 부족함
        // O(nlogn) => 500000
        // nlogn은 내가 아는 건 이진 탐색 뿐이다.
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 레슨 수 N, 블루레이 개수 M 입력 받기
        // 강의 배열 입력 arr
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
 
        // 제일 큰 용량의 강의 저장 변수 max
        int max = 0;
        // 모든 강의 용량 저장 변수 sum
        int sum = 0;
 
        // N만큼 반복하며 N 크기의 배열에 강의 길이 입력 받기
        int[] lectures = new int[N];
        input = br.readLine().split(" ");
        for (int i=0; i<N; i++) {
            int n = Integer.parseInt(input[i]);
            // lecture[i] = arr
            lectures[i] = n;
            // max = Math.max(max, arr[i])
            max = Math.max(max, n);
            // sum = arr[i-1] + arr[i]
            if ( i == 0 ) sum = n;
            else sum = sum + n + Integer.parseInt(input[i-1]);
        }
 
        // 이진탐색(강의 배열, 최대값, 누적합, 블루레이 개수)
        binary_search(lectures, max, sum, M);
    }
 
    // 이진탐색 (강의 배열, 최대값, 누적합, 블루레이 개수)
    public static void binary_search(int[] lectures, int minimum, int maximum, int M) {
        // 최소값 = 최대값
        int min = minimum;
        // 최대값 = 누적합
        int max = maximum;
        // 반복문 ( 최소값이 최대값보다 작거나 같은 동안 )
        int answer = 0;
        while (min<=max) {
            // 중간값 = (최소값+최대값) / 2
            int mid = (min+max) /2;
            // 카운트 = 0;
            int count = 0;
            // 합계 = 0;
            int sum = 0;
            //
            // 반복문 (강의 배열 길이만큼) {
            for (int i=0; i< lectures.length; i++) {
                // i 부터 더하자
                if ( sum + lectures[i] > mid ) {
                    count+=1;
                    sum = 0;
                }
 
                // 만약 합계가 중간값과 같거나 크다면?
                sum += lectures[i];
                    // 카운트 증가
                    // 합계 초기화
            }
            //
            // 만약 합계가 0이 아니라면?
            if (sum !=0) {
                // 카운트 증가
                count++;
            }
            //
            // 만약 카운트가 블루레이 개수보다 작거나 같다면?
            if (count <= M) {
                // 최대값 = 중간값-1
                max = mid-1;
                answer = mid;
            }
            //
            // 만약 카운트가 블루레이 개수보다 크다면?
            if (count > M) {
                // 최소값 = 중간값+1
                min = mid+1;
            }
        }
        System.out.println(answer);
        // 탐색이 모두 끝나면 출력
    }
}

 

주석은 처음에 쓰고 안 지운 내용이라 틀렸으니 무시