영화제에서 겹치지 않게 관람할 수 있는 최대 영화 개수를 구하는 C++ 프로그램

여러 나라의 다양한 영화를 상영하는 영화제가 진행 중이라고 가정해 보겠습니다. 한 참석자가 서로 겹치지 않는 영화를 최대한 많이 관람하고 싶어 할 때, 우리는 이 참석자가 총 몇 편의 영화를 온전히 볼 수 있는지 계산하는 프로그램을 작성해야 합니다.

구조체 설계

먼저 영화 정보를 담는 Movie 구조체는 다음과 같은 멤버 변수를 가집니다.

영화의 시작 시간(timeBegin)
영화의 상영 길이(duration)
영화의 종료 시간(timeEnd)

그리고 영화제 정보를 담는 Festival 구조체는 다음 멤버들을 포함합니다.

영화제에서 상영되는 영화의 총개수
Movie 타입 객체들을 담는 배열 (배열 크기는 영화 개수와 동일)

우리는 여러 영화의 시작 시간과 상영 길이를 각각 담고 있는 두 배열 'timeBegin'과 'duration'으로 Festival 객체를 생성하고 초기화해야 합니다. 정수 n은 전체 영화의 개수를 의미하며, 객체 초기화에 함께 사용됩니다. 이후 이 객체를 활용해 참석자가 처음부터 끝까지 완전히 관람할 수 있는 영화가 몇 편인지 계산합니다.

예시

입력이 timeBegin = {1, 3, 0, 5, 5, 8, 8}, duration = {3, 2, 2, 4, 3, 2, 3}, n = 7이라면 출력 결과는 4입니다.

즉, 참석자는 해당 영화제에서 총 4편의 영화를 온전히 관람할 수 있습니다.

풀이 접근 방법

이 문제는 대표적인 '활동 선택 문제(Activity Selection Problem)' 유형으로, 탐욕(Greedy) 알고리즘을 적용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 영화를 종료 시간 기준으로 오름차순 정렬한 뒤, 직전에 선택한 영화가 끝난 시점 이후에 시작하는 영화만 순서대로 선택하는 것입니다. 종료가 빠른 영화부터 고르면 남는 시간이 최대한 많아져 전체 관람 횟수를 극대화할 수 있기 때문입니다.

단계별 풀이 과정은 다음과 같습니다.

Movie 구조체 정의 — timeBegin, duration, timeEnd 세 멤버 변수를 선언하고, 비교 연산자 '<'를 오버로딩하여 다른 Movie 객체와 비교할 때 timeEnd 값을 기준으로 삼도록 합니다.
Festival 구조체 정의 — 영화 개수를 저장할 count와 Movie 객체들을 담는 movies 배열을 멤버로 선언합니다.
initialize() 함수 구현 — 배열 timeBegin, duration과 정수 n을 매개변수로 받습니다.
- 새로운 Festival 객체 filmFestival을 생성합니다.
- filmFestival의 count를 n으로 설정합니다.
- i를 0부터 count 미만까지 반복하면서 다음을 수행합니다.
  - Movie 타입의 임시 객체 temp를 생성합니다.
  - temp의 timeBegin은 timeBegin[i]로, duration은 duration[i]로 설정합니다.
  - temp의 timeEnd는 timeBegin[i] + duration[i]로 계산합니다.
  - temp를 filmFestival의 movies 배열에 추가합니다.
- 완성된 filmFestival 객체를 반환합니다.
solve() 함수 구현 — Festival 타입 변수 fest를 매개변수로 받습니다.
- 결과값 res를 0으로 초기화합니다.
- fest의 movies 배열을 종료 시간 기준으로 정렬합니다.
- 마지막 관람 종료 시간을 나타내는 timeEnd를 -1로 초기화합니다.
- i를 0부터 fest->count 미만까지 반복하면서 다음을 검사합니다.
  - 만약 fest->movies[i]의 timeBegin이 현재 timeEnd보다 크거나 같다면:
    - res를 1 증가시킵니다.
    - timeEnd를 fest->movies[i]의 timeEnd 값으로 갱신합니다.
- 최종 res 값을 반환합니다.

구현 코드

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

#include<bits/stdc++.h>

using namespace std;

struct Movie {
   int timeBegin, duration, timeEnd;
   bool operator<(const Movie& another) const {
      return timeEnd < another.timeEnd;
   }
};

struct Festival {
   int count;
   vector<Movie> movies;
};
Festival* initialize(int timeBegin[], int duration[], int count) {
   Festival* filmFestival = new Festival;
   filmFestival->count = count;
   for (int i = 0; i < count; i++) {
      Movie temp;
      temp.timeBegin = timeBegin[i];
      temp.duration = duration[i];
      temp.timeEnd = timeBegin[i] + duration[i];
      filmFestival->movies.push_back(temp);
   }
   return filmFestival;
}
int solve(Festival* fest) {
   int res = 0;
   sort(fest->movies.begin(), fest->movies.end());
   int timeEnd = -1;
   for (int i = 0; i < fest->count; i++) {
      if (fest->movies[i].timeBegin >= timeEnd) {
         res++;
            timeEnd = fest->movies[i].timeEnd;
      }
   }
   return res;
}

int main(int argc, char *argv[]) {
int timeBegin[] = {1, 3, 0, 5, 5, 8, 8};
int duration[] = {3, 2, 2, 4, 3, 2, 3};
Festival * fest;
fest = initialize(timeBegin,duration, 7);
cout << solve(fest) << endl;
return 0;
}

입력

int timeBegin[] = {1, 3, 0, 5, 5, 8, 8};
int duration[] = {3, 2, 2, 4, 3, 2, 3};
Festival * fest;
fest = initialize(timeBegin,duration, 7);