C++ 코딩테스트 강좌, 블루레이 만들기

안녕하세요! 이번 포스팅에서는 C++ 코딩테스트를 대비하기 위한 알고리즘 문제를 풀어보며, ‘블루레이 만들기’라는 주제에 대해 심도 있게 탐구해 보겠습니다. 이 문제는 주로 동적 프로그래밍과 이분 탐색을 활용하여 접근할 수 있습니다. 함께 코드를 작성하고, 단계별로 문제를 해결하는 과정을 따라가 봅시다.

문제 설명

블루레이는 영화와 같은 미디어 콘텐츠를 저장하고 재생하는 디스크입니다. 한 사용자에게 특정 영화 목록이 주어지고, 이 목록의 영화를 블루레이에 저장하기 위해 최대한 효율적으로 저장하려고 합니다. 사용자는 각 블루레이에 저장할 수 있는 영화의 최대 시간을 설정할 수 있으며, 이를 이용해 블루레이 몇 개가 필요한지를 최소화하려고 합니다.

문제 정의

    영화 목록은 N개의 영화로 구성되어 있으며, 각 영화의 길이는 A[i]와 같이 주어집니다. 이제 우리는 기간 T로 제한된 블루레이를 사용하여 최소한의 블루레이 수로 모든 영화를 저장하고자 합니다. 
    주어진 제약 조건을 활용하여 블루레이의 개수를 알고리즘으로 계산하는 문제를 해결합시다.

입력

  • 첫 번째 줄에 영화의 개수 N (1 ≤ N ≤ 1000)과 최대 블루레이에 저장할 수 있는 시간 T (1 ≤ T ≤ 10000)가 주어집니다.
  • 두 번째 줄에 각 영화의 길이를 나타내는 N개의 정수가 주어집니다. 각 영화의 길이는 1 이상 T 이하입니다.

출력

필요한 블루레이의 최소 개수를 출력합니다.

문제 접근 방식

문제를 해결하기 위해서 우리는 다음과 같은 단계를 따릅니다:

  1. 이분 탐색을 활용하여 가능한 블루레이의 최대 저장 시간 범위를 설정합니다.
  2. 각 블루레이에 영화를 저장하는 데 필요한 블루레이 수를 카운트합니다.
  3. T 시간을 초과하는 경우 블루레이 개수를 증가시키고, T 이하인 경우 최대 블루레이 저장 시간을 조정합니다.
  4. 최종적으로 필요한 블루레이 개수를 출력합니다.

코드 구현

    
    #include <iostream>
    #include <vector>
    #include <algorithm>

    using namespace std;

    int countBluRays(const vector<int>& movies, int maxTime) {
        int count = 1; // 최소 1개의 블루레이는 필요
        int currentTime = 0;

        for (int movie : movies) {
            if (currentTime + movie > maxTime) {
                count++; // 새로운 블루레이 필요
                currentTime = movie; // 현재 영화 대입
            } else {
                currentTime += movie; // 현재 블루레이에 영화 추가
            }
        }
        return count;
    }

    int main() {
        int N, T;
        cin >> N >> T;

        vector<int> movies(N);
        for (int i = 0; i < N; i++) {
            cin >> movies[i];
        }

        // 이분 탐색을 통한 블루레이 최대 시간 결정
        int low = *max_element(movies.begin(), movies.end());
        int high = accumulate(movies.begin(), movies.end(), 0);
        int result = high;

        while (low <= high) {
            int mid = (low + high) / 2;
            int requiredBluRays = countBluRays(movies, mid);

            if (requiredBluRays <= T) {
                result = mid; // 블루레이 최대 시간을 줄일 수 있다.
                high = mid - 1;
            } else {
                low = mid + 1; // 블루레이 최대 시간을 늘린다.
            }
        }

        cout << result << endl;
        return 0;
    }

코드 설명

위 코드는 다음의 주요 부분으로 구성되어 있습니다:

  1. countBluRays 함수: 주어진 최대 블루레이 시간(maxTime)에 따라 영화를 저장하기 위해 필요한 블루레이의 개수를 계산합니다. 각 영화를 순회하며 현재 블루레이에 담을 수 있는지 확인하고, 필요시 블루레이를 추가합니다.
  2. main 함수: 입력으로 영화 개수 N과 블루레이의 최대 시간 T를 받고, 영화의 길이를 저장합니다. 이어서 이분 탐색을 통해 모든 영화를 저장하는 데 필요한 최소 블루레이 시간을 찾아냅니다.

알고리즘 복잡도

위 알고리즘의 시간 복잡도는 O(N log S)입니다. 여기서 N은 영화의 개수이고, S는 영화 길이의 합입니다. 이분 탐색 과정에서 매번 모든 영화를 순회하므로 효율적입니다.

결론

이번 포스팅에서는 ‘블루레이 만들기’라는 코딩 문제를 통해 이분 탐색과 동적 프로그래밍의 기초를 쉽게 이해했습니다. 알고리즘 문제를 해결하는데 있어서는 문제의 본질을 파악하고, 적절한 접근 방식을 찾는 것이 중요합니다. 연습을 통한 경험이 쌓이게 되면, 더 복잡한 문제들도 수월하게 해결할 수 있을 것입니다. 다음 포스팅에선 좀 더 다양한 문제들에 대해 탐구해 보겠습니다!

© 2023 C++ 코딩테스트 강좌