[node.js,백준]2343 - 기타 레슨

목차

 

 

 문제

링크

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

 

문제

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

 

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

 

주저리

이분 탐색을 이용해 푸는 문제

블루레이 갯수는 정해져있고 거기서 크기를 최소로하여 구하는 문제이다.

right는 곡의 길이의 합을 구하면되지만

left가 완전히 이해가되지않는다 left가 0으로할땐 위의 스크린샷처럼 틀리게되고

left가 곡의 하나의 최댓값으로 해두면 정답이 된다.

left right를 잘 산정하고 이분탐색 해주면 끝

 

풀이

 이진 탐색 초기화

• - `left`는 가능한 최소 블루레이 길이로, 가장 긴 비디오 길이로 설정합니다.
• - `right`는 모든 비디오 길이의 합으로 설정합니다.

 이진 탐색 실행

• - `left`와 `right` 범위 내에서 중간값 `mid`를 계산합니다.
• - `go(mid)` 함수를 호출하여, `mid` 길이를 최대로 하는 블루레이가 몇 개 필요한지 계산합니다.
• - 필요한 블루레이 개수가 `M`보다 많으면, `mid`는 너무 작다는 뜻이므로 `left`를 `mid + 1`로 조정합니다.
• - 그렇지 않으면 `right`를 `mid - 1`로 조정하며, 결과값 `result`를 `mid`로 갱신합니다.

 go(blueSize) 함수

• - 주어진 `blueSize`를 최대 길이로 하여 비디오들을 블루레이에 분배할 때, 필요한 블루레이의 수를 계산합니다.
• - 비디오 배열을 순회하며, 현재 블루레이의 길이 합이 `blueSize`를 초과하지 않도록 비디오를 추가합니다.
• - 한 블루레이에 더 이상 비디오를 추가할 수 없을 때, 블루레이의 수를 증가시킵니다.

 결과 출력

• - 최종적으로 `result`에 저장된 값이 주어진 `M`개의 블루레이에 모든 비디오를 담을 수 있는 최소의 최대 길이가 됩니다.

 코드

// 기타 레슨
var fs = require('fs');
// var input = fs.readFileSync('/dev/stdin').toString();
let input = `5 4
1 5 9 3 10`

let real = input.trim().split("\n");
let [first, ...rest] = real;
let [N, M] = first.split(" ").map(Number);

/**
 * 갯수를 가급적 줄일꺼고
 * 크기가 모르는 상태
 */
async function solution() {
    let arrs = rest[0].split(" ").map(Number);
    // console.log({ N, M, arrs })
    let arrsLength = arrs.length;
    let left = 0;
    let right = 0;

    for (let row of arrs) {
        if (left < row) left = row;
        right += row;
    }


    function go(blueSize) {
        let count = 0;

        let innerIndex = 0;
        while (innerIndex !== arrsLength) {
            let cur = 0;
            // console.log({ innerIndex, cur })
            count++
            do {
                cur += arrs[innerIndex];
                innerIndex++;
                // console.log('cur,arrs.innerIndex', cur, arrs[innerIndex])
            }
            while (cur + arrs[innerIndex] <= blueSize)
        }


        return count
    }

    let result;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2)
        if (go(mid) > M) {
            left = mid + 1
        }
        else {
            result = mid;
            right = mid - 1
        }
    }
    console.log(result);
}

solution();