미팅수 최대 문서

이 문제는 greedy method 로 널리 알려져 있는 문제이지만 다이나믹 프로그래밍으로도 좋은 예인 것 같습니다. 다이나믹 프로그램으로 접근하는 경우 어떤 미팅에서 최대가 되는지는 조금 생각해 보아야 할 듯 합니다.

1. 설명

선제 조건: 종료 시간을 기준으로 정렬되어 있다.

• 종류: 0/1 knapsack 류
• 점화 식:dy[i] : i 시간 까지의 meeting 의 최대 수이고 ,
• 가장 늦은 종료시간이 n 이라면 답은 dy[n].

예를 들어 , 시작과 종료시간이 s , e 라면

추가되는 회의를 포함하는 경우 아닌 경우 중 최대

1. dy[e - 1] : 회의를 포함시키지 않는 경우
2. dy[s] + 1 : 회의를 포함 시킬 경우

두가지 경우 중 최대가 dy[e]

---

차례대로 과정을 보자.( 그림을 잘못 그려서 m 배열이 dy 배열 ) 풀이를 간단히 하기 위해 미팅 시간은 0 부터 9 까지 입력된다고 가정하자.

1. 첫번 째 회의 확장

   

   • 작업의 끝이 3 이므로 0 에서 2 까지는 0 으로 채움
   • dy[3] = max( dy[3-1] , dy[1] + 1)

2. 두번 째 회의 확장

   

3. 세번 째 회의 확장

   

4. 네번 째 회의 확장

   

5. 다섯번 째 회의 확장

   

2. 시간 복잡도

O(n)

출처:dovelet