백준 BOJ 1931번

---

접근 방법

 

탐욕(Greedy) 알고리즘의 대표적인 문제다. 그리디 알고리즘은 간단하게 뒤는 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 각 단계의 최선의 선택이 전체적으로도 최선이길 바라는 기법인데, 당연하게도 모든 경우에서 적용할 수는 없다.

그리디 알고리즘을 사용할 수 있는 유형의 문제들이 있는데, 바로 활동 선택 문제와 분할 가능 배낭 문제다. 이번 문제는 이 중에서 활동 선택 문제로, 한 자원이 하나의 활동만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제다. 이 문제에서는, 이전의 선택 결과가 이후의 결과에 영향을 미치지 않기 때문에 적용할 수 있다.

 

그렇다면, 그리디 알고리즘을 이 문제에 어떻게 적용해야 하는가?

 

먼저 생각해야 할 것은, 이전의 선택 결과가 이후의 결과에 영향을 미치지 않으려면 종료 시간이 다른 회의의 시작 시간과 겹치면 안된다는 것이다. 그리고 최대한 많은 활동을 선택하려면 종료 시간이 빠른 것을 선택하는게 각 단계에서 최선일 것이다. 

 

그래서 각 회의를 종료 시간을 기준으로 정렬하는 것이 포인트다.

출처 : https://myeongju00.tistory.com/29

종료 시간을 기준으로 정렬한 위의 표에서 보면 N1(1,4), N4(5,7), N8(8,11), N11(12,14)로, 최대 회의 가능한 수는 4개다.

 

1. 종료 시간을 기준으로 정렬한다.
2. 종료시간이 가장 빠른 것을 선택한다.
3. 종료 시간과 겹치는 것을 제외하고 2. 를 한다.

주의사항은 종료 시간으로 정렬할 때, 종료 시간이 같다면 시작 시간이 빠른 순으로 정렬해야 한다는 것이다.

 

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      int N = Integer.parseInt(br.readLine());
      int[][] arr = new int[N][2];
      StringTokenizer  st;

      for(int i = 0; i < N; i++){
         st = new StringTokenizer(br.readLine(), " ");
         arr[i][0] = Integer.parseInt(st.nextToken());
         arr[i][1] = Integer.parseInt(st.nextToken());
      }

      Arrays.sort(arr, new Comparator<int[]>(){
         @Override
         public int compare(int[] o1, int[] o2){
            if(o1[1] == o2[1]) return o1[0] - o2[0];
            return o1[1] - o2[1];
         }
      });

      int count = 0;
      int end = 0;
      for(int i = 0; i < N; i++){
         if(end <= arr[i][0]) {
            count++;
            end = arr[i][1];
         }
      }
      System.out.println(count);
   }
}