전형적인 Dynamic Programming 문제... 라고 생각했는데,

사실 DP부분은 너무 간단한거라(전형적인 2차원) 아무 생각 없이 제출했다가 틀렸다.

내가 실수한 부분은 정렬 순서를 잘못 생각한 것이었는데,

다음 중 옳은 접근은 어떤 것일까?

1. 각 선분(구름)을 오른쪽 끝 좌표 기준으로(같을 경우 왼쪽 끝을 기준, 오름차순) 오름차순 정렬한다.

2. 각 선분(구름)을 왼쪽 끝 좌표 기준으로(같을 경우 오른쪽 끝을 기준, 오름차순) 오름차순 정렬한다. 

풀이 보기2

DP부분은 정말정말 쉽지만 그래도 모른다면...

풀이 보기 2


신고