a번마을에서 b번마을까지 가는 상자를

양끝점이 x=a,x=b인 막대기라고 생각하였습니다.

그리고 이를 시점 a와 길이 l로 묶은 쌍(a,l)로 생각하고 접근했습니다.

만약 길이가 다른, 겹치는 두개의 막대가 있다면, 긴거를 고르는것보단 짧은걸 고르는게 정답을 보장할수 있습니다.

왜냐하면 짧은거를 고르는 경우에 여백이 더 생기때문에 무조건 더 많은수의 막대가 들어갈수밖에 없기 때문이죠.

막대의 길이가 같은경우, 가장 끝쪽에 있는 A막대기를 놓지 않는경우 최적해를 갖는다 가정합니다. 그렇다면 A막대기와 겹치는 막대가 하나 존재합니다. (만약 겹치는 막대가 존재하지 않는다면, 무조건 A를 놓는편이 하나 많아서 모순입니다.)이를 약간 옮겨보면, 놓지 않았다고 가정한 막대기를 놓은경우가 됩니다. 따라서 가장 끝쪽에있는 막대기를 greedy하게 반복적으로 선택해가면 최적해가됩니다.

따라서 stable하게 시점,길이를 기준으로 정렬해둔다음,

길이=1일때, 시점순서로 막대를 하나씩 두어보고,

길이=2일때, 길이=3일때... 해나가다보면

결과적으로 막대를 고를수있는 최대의 수가 나오게됩니다.

이러한 알고리즘으로 계산을 했지만, 틀렸습니다가 나옵니다.

어디서 잘못한건가요?