9. 뮤직비디오 (결정 알고리즘)

1. 문제

DVD를 담을 수 있는 최소 용량 크기(length)를 출력하세요.

N은 곡의 개수

M은 곡을 담을 DVD의 수

다음줄에는 N개 각각 곡의 길이

 

2 - 1. 나의 풀이

최소 용량 크기(length)를 맨 처음 1이라고 가정하면서 최소 용량 크기 (length) 를 1씩 더해서 계속 검증

1. sum에 곡의 길이를 누적합 한다.

2. sum += arr[i]를 하고 최소 용량의 크기보다 크면 M과 비교할 변수 count를 +1 하고 sum을 arr[i]로 바꾼다.

3. sum이 m 보다 크면 이번 반복문에서 설정한 최소 용량의 크기는 부족하므로 break; 하고 최소 용량 크기를 +1 한다.

4. 반복문이 끝나면 count+1을 해줘야한다. 이유는 맨 마지막 값을 누적합하고 for문이 끝났을 때 최소 용량 크기가 적절하다면 sum과 length를 비교하는 조건문에서pass되어 count++이 이뤄지지 않기 때문이다.

5. 마지막으로 count 가 m 보다 작거나 같다면 그 값이 최소 용량 크기이다.

만약 용량의 크기가 30이면 1234567 89를 두번에 나누어서 저장할 수도 있지만 세 번에도 나누어 저장할 수 있다.

나는 용량의 크기를 1부터 +1씩 증가하면서 최소 용량 크기를 찾고있기 때문에 count가 m보다 작거나 같게 나오는 용량 크기가 있다면 그 값이 바로 최소 용량 크기이다. 

 

2 - 2. 나의 코드

package Sort;
import java.util.*;

public class Sort_09 {
    public static int solution(int n, int m, int[] arr) {
        int length=1;
        int count = 0;
        int sum = 0;

        while(true){ //while(true)는 탈출 경로를 잘 작성해야한다. 되도록 쓰지말자
            count =0;
            sum =0;

            for (int i = 0; i < n; i++) {
                int tmp = arr[i];
                sum += tmp;

                if(length < sum) { //sum이 length를 뛰어넘으면
                    count++; //여기서 count++했는데 이미 m보다 높으면 탈락
                    if(count > m) break;
                    sum = tmp;
                }
            }
            //for문 종료 후
            count++;
            if(count <= m) return length;
            else length++;
        }
        return length;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println(solution(n,m,arr));
    }
}

 

3 - 1. 강의 풀이

결정 알고리즘은 주어진 입력값을 활용해서 그 안에 답이 있다는 확신이 있을 때 사용한다.

입력값의 누적합 안에 최소 용량의 크기가 있기에 결정 알고리즘을 사용한다.

 

3 - 2. 강의 코드

package Sort;
import java.util.*;

public class Decision_Algorithm {
    public static int count(int[] arr, int capacity) { //용량 확인 작업
        int cnt=1; //DVD 장수
        int sum=0;
        for(int x : arr){
            sum += x;
            if (sum > capacity) {
                cnt++;
                sum = x;
            }

            /*if (sum + x > capacity) {
                cnt++;
                sum = x;
            }else sum+=x;*/
        }
        return cnt;
    }

    public static int solution(int[] arr, int n, int m) {
        int answer = 0;
        int lt = Arrays.stream(arr).max().getAsInt(); //max()는 OptionalInt로 감싸진다. 이걸 벗겨내야함
        int rt = Arrays.stream(arr).sum(); //sum()은 옵셔널이 아니라 int를 반환해서 안벗겨도됨

        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            if(count(arr, mid) <= m){
                answer = mid;
                rt = mid - 1; //mid 보다 더 적은 용량으로 담을 수 있는지.
            }
            else lt = mid + 1;
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        int sum =0;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        System.out.println(solution(arr, n, m));
    }
}

 

4. 얻어갈 점

결정 알고리즘 부분 공부를 많이 해야겠다.