문제
처음 생각했던 방식
이 문제와 비슷한 문제를 풀어본 적이 있었다.
리트 코드 문제였는데 연결해서 가장 긴 체인 수를 구하는 문제이다. 이 때에는 다이나믹 프로그래밍 방법으로 해결하였다.
[[1, 2], [7, 8], [4, 5]]를 설명하면
처음으로 left를 기준으로 정렬한다. [[1, 2], [4, 5], [7, 8]]이 된다.
문제에서 조건으로 -1000 <= lefti < righti <= 1000 라고 명시했으므로 1000을 더하여 음수를 제거해준다. 결국 0 <= lefti < righti <= 2000이 될 것이다.
그럼 [[1, 2], [4, 5], [7, 8]]은 [[1001, 1002], [1004, 1005], [1007, 1008]]이 될 것이다.
이제 dp를 사용해보자
| 1001 | 1002 | 1003 | 1004 | 1005 | 1006 | 1007 | 1008 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 |
dp테이블에는 가장 최대값을 저장해둔다면 [4, 5]일 때 [4]에서 가장 최대값 + 1과 바로 이전의 값을 비교하면 된다.
여기서 [4, 5]~ [7, 8]처럼 6이라는 빈 공간이 생기는데 이 때에 현재 최대값을 저장해주는 방법으로 하였다.
하지만 여기서 조건은 -1000~ 1000이라는 조건이 있기 때문에 가능하였다.
백준 문제에서는 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다. -1000,1000과 비교했을 때 엄청 큰 수이다. 처음 DP문제로 풀려고 했으나 TLE가 발생하였다.
정렬
직관적으로 이해해야 했다. 종료시간 순으로 정렬하고 또한 종료시간이 같을 수도 있으니까 같을 때 시작시간 순으로 정렬을 하게 되면 항상 최선의 방법을 구할 수가 있게 된다.
이렇게 체인같은 문제가 나오면 dp가 아닌 정렬 후 그리디로 풀어야 겠다.
