[백준/JAVA] 2343번: 기타 레슨

🔺 문제

2343번: 기타 레슨

 

🔺 코드

import java.util.*;
import java.io.*;
 
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 M = Integer.parseInt(st.nextToken());   // 블루레이 수
 
        int[] arr = new int[N];
        int start = 0;  // 시작 인덱스
        int end = 0;    // 🔔 레슨 길이 총합으로 설정
 
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < N ; i++) { 
            arr[i] = Integer.parseInt(st.nextToken());
 
            if(arr[i] > start) start = arr[i];   // 🔔 레슨 최댓값을 시작 인덱스로 저장
            end += arr[i];                       // 🔔 모든 레슨의 총합을 종료 인덱스로 저장
        }
 
        while(start <= end) {
            int mid = (start + end) / 2;
 
            int sum = 0;
            int cnt = 0;
 
            // 🔔 mid 값으로 모든 레슨 저장할 수 있는지 확인 🔔
            for(int i = 0 ; i < N ; i++) {
                if(sum + arr[i] > mid) { // 반복문 통해 레슨 길이 더하기
                    cnt++;
                    sum = 0;
                }
                sum += arr[i];
            }
 
            if(sum != 0)
                cnt++;
 
            if(cnt > M)  start = mid + 1;
            else        end = mid - 1;
        }
 
        System.out.println(start);
    }
}

✅ 해결 아이디어
- 이진 탐색
▹ 시작 idx = 레슨 길이 최댓값
▹ 종료 idx = 모든 레슨 길이의 합

• 중앙값 크기로 모든 레슨을 저장할 수 있으면 종료 인덱스 = 중앙값 - 1 (왼쪽 데이터셋)
• 중앙값 크기로 모든 레슨을 저장할 수 없으면 종료 인덱스 = 중앙값 + 1 (오른쪽 데이터셋)

=> 9 ~45 사이에서 블루레이 크기의 최솟값을 이진 탐색으로 찾기

 

---

🔺 다른 풀이들

[BOJ] 백준 2343 기타 레슨

[백준 2343번] 기타 레슨 (java)

---

💬 느낀 점

어렵구나...

 

1회독	2회독	3회독	4회독	5회독
V	6/17

 

 

(+ 6/17 2회독)

코드

import java.util.*;
import java.io.*;
 
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 M = Integer.parseInt(st.nextToken());   // 블루레이
 
        int[] arr = new int[N];
        int start = 0;  // 시작 인덱스 = 레슨 최댓값
        int end = 0;    // 종료 인덱스 = 배열 총합
 
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < N ; i++) { 
            arr[i] = Integer.parseInt(st.nextToken());
            end += arr[i];                      // 모든 레슨의 총합을 종료 인덱스로 저장
            start = Math.max(start, arr[i]);    // 레슨 최댓값을 시작 인덱스로 저장
        }
 
        while(start <= end) {
            int mid = (start + end) / 2;
 
            int sum = 0; // 레슨 합
            int cnt = 0; // 현재 사용한 블루레이 개수
 
            // mid 값으로 모든 레슨 저장할 수 있는지 확인
            for(int i = 0 ; i < N ; i++) {
                if(sum + arr[i] > mid) {    // 현재 블루레이에 저장할 수 없어 새 블루레이로 교체
                    sum = 0;
                    cnt++;
                }
                sum += arr[i]; // sum에 현재 레슨 시간 값 더하기
            }
 
            if(sum != 0)
                cnt++;
                
            if(cnt > M) // 중간 인덱스값으로 모든 레슨 저장이 불가능한 경우
                start = mid + 1;
            else // 중간 인덱스값으로 모든 레슨 저장이 가능한 경우
                end = mid - 1;
        }
 
        System.out.println(start); // 시작 인덱스 출력
    }
}

 

위 코드보다 이 코드로 하는 게 나을 거 같다.

큰 차이는 없지만