[더블릿] Koi_Delivery 배송 문제

더블릿의 배송 문제는 다음과 같이 해결한다.

위와 같은 경우입니다.
답은 150인데, 현재 소스는 120을 출력하고 있습니다.
즉, 처음 선택할때 1 6 40에 해당하는 40에서 30만큼을 선택하기 때문에
끝날때까지 택배 가방(님이 가방으로 표현하셔서 그렇게 얘기하겠습니다 ㅋ) 용량이 30으로 밖에 유지될 수 없어서
중간에 크게 옮겨실어나를수 있음에도 불구하고 계속 용량 30밖에 못사용하는거죠.

그럼 어떻게 하냐...
s에서 택배꾸러미를 받아서 e에서 택배를 내려놓는다고 할때
s에서부터 e-1까지 해당 택배꾸러미를 계속 들고 있어야 합니다. (e는 내려놓는곳이니까 제외하죠)
해당 택배꾸러미의 용량을 w라고 하면 s부터 e까지는 택배를 기본 여유용량 C에서 w만큼 뺀 것입니다.
즉, 예를 들면 원래 가방용량이 40이고 s=2 e=4라고 하고 들고다닐 택배꾸러미 용량w=20이라고 하면 (택배를 주고받는 곳이 6개 있다고 합시다)
1    2    3   4   5   6
40 20 20 40 40 40 <-이 됩니다. (각 지점에서의 가방의 여유용량)

그럼 다음번에 1-4구간에서 택배용량이 30만큼 되는걸 나르려고 해도 2-3구간의 여유용량이 20밖에 되지 않으므로 20만큼만 나를 수 있습니다.

그리고 이러한 알고리즘이 가능하게 된 것은 처음에 도착지점을 기준으로 오름차순 정렬을 하기 때문입니다. (두번째 우선순위로는 출발지점을 기준으로 오름차순 정렬인거죠)
그니까 이 문제는 도착지점이 1쪽에 가까울수록.. 그니까 택배를 어디서 받았든간에(출발지점이 어떻든간에) 1에 가까운 도착지점에 택배를 내릴 수록 더 많은 택배를 실어날을 수 있습니다.

저도 우리 슬렉의 private channel(가입하신 스터디그룹 ㅋ)에서 잘 몰라서 계속 물어보고 풀었던 문제입니다.
저두 도움 많이 받아서 글 좀 남겨봤습니다 ㅎ;
슬렉 자주 들어오세요~!

아 그리고 정보올림피아드 문제의 경우는 http://www.jungol.co.kr/bbs/board.php?bo_table=pba... 여기 사이트 가서 회원가입하시고 제출하시면 틀린 테스트케이스가 뭔지 보여줍니다. 틀린 테케를 생각하는것도 능력이겠지만... 그냥 연습때에 틀린테케 보는건 정신건강에 아주 이롭다고 생각됩니다.ㅋㅋ

<해결방법>

도착지점 기준으로 정렬하여 해결한다.