시작 시간과 끝나는 시간이 보다 작거나 같은 자연수 또는 0인 문제입니다.
dp 배열을 생성한다면, 아마 메모리 초과로 실패가 뜰 것입니다.
그렇습니다... dp인줄 알았으나 그리디였던 문제였습니다.
그리디로 풀려면 회의 시간들을 어떻게 정렬해야 할까요?
사실 이 문제의 예제에 힌트가 있었는데요,
바로 끝나는 시간을 기준으로 정렬하는 것입니다.
이전 회의가 끝나는 시간 <= 현재 회의가 시작하는 시간이라면
이전 회의와 현재 회의는 겹치지 않을 것입니다.
따라서 끝나는 시간을 기준으로 오름차순 정렬을 한 다음에
차례로 이전 회의의 끝나는 시간과 현재 타겟의 시작 시간을 비교하고
만약 이전 회의의 끝나는 시간 <= 현재 타겟의 시작 시간이 성립한다면
result +=1을 한 후에 이전 회의의 끝나는 시간을 현재 타겟의 시작 시간으로 대체해주면 됩니다.
latest_end = 0
(1, 4) 에서 0 <= 1 이므로 latest_end = 4
(5, 7) 에서 4 <= 5 이므로 latest_end = 7
(8, 11) 에서 7 <= 8 이므로 latest_end = 11
(12, 14) 에서 11 <= 12 이므로 latest_end = 14
하지만 이 문제에서는 한 가지를 더 고려해주어야 합니다.
만약 (2, 2)를 체크한 후에 (1, 2)를 체크하면 어떻게 될까요?
2 <= 1이 성립하지 않으므로 (1, 2)는 카운트되지 않는 문제가 발생합니다.
따라서 끝나는 시간을 기준으로 오름차순 정렬을 한 다음에,
시작 시간을 기준으로 오름차순 정렬까지 해주어야 합니다.
dp로 풀었다면 문제가 되지 않았겠지만, 그리디는 현재의 선택이 나중에 미칠 영향에 대해선 고려하지 않으므로 어떤 순서로 체킹할 것인지 잘 고려해야 합니다.
n = int(input())
l = [tuple(map(int, input().split())) for _ in range(n)]
l.sort(key=lambda x: (x[1], x[0])) # 끝나는 시간 -> 시작 시간 순으로 오름차순 정렬
result = 0
latest_end = 0
for li in l:
if li[0] >= latest_end:
result += 1
latest_end = li[1]
print(result)
