백준 #1931

문제풀이는 세가지로 생각할수 있다.

1. 시작시간이 빠른 순서대로
2. 끝나는 시간이 빠른 순서대로
3. 시작과 끝의 차이가 작은 순서대로

1,3은 간단히 생각해도 반례가 존재해서 2번으로 풀어야 할 것 같다.

2번 방법에 대한 최적여부를 검증해보자.

 

첫번째는 종료시간이 빠른 값이 최적해에 포함됨을 증명하는 것이다.

종료시간과 관계없는 최적해 S가 있다고 가정하자. 만약 S[0]을 빼고 종료시간이 빠른 값을 넣는다면 S >= S'이므로 귀류법으로 증명 가능하다. 

 

두번째는 최적 부분 구조의 속성이다. 부분에서 최적해를 구하는것이 전체 최적해임을 증명해야한다. 근데 이건 문제 특성상 하나를 선택했을 때 그 나머지를 선택하는데 영향을 주지 않으므로 당연하게 알 수 있다. 

 

이 둘을 합치면 첫번째 선택을 할 때 종료시간이 빠른 값을 선택한다. 그리고 그뒤에도 계속 종료시간이 빠른 값을 선택하는 것이 최적해이다.

import sys

n = int(input())
times = []

for _ in range(n):
    time = list(map(int,sys.stdin.readline().split()))
    times.append(time)

times.sort(key=lambda x: (x[1],x[0]))
total = 1
current_time = times[0][1]
index = 0

while True :
    index += 1 
    if index == len(times):
        break
    if current_time <= times[index][1] and current_time <= times[index][0]:
        current_time =  times[index][1]
        total += 1


print(total)