백준 31964 반품 회수 문제 풀이
백준 온라인 저지, 31964번: 반품 회수
도입
문제 시나리오 상의 시간 흐름은 세 유형으로 구분할 수 있다. 택배 회수를 위해 출발점에서 떠나는 시간, 택배 회수를 위해 각 점에서 대기하는 시간, 택배 회수를 마치고 출발점으로 되돌아오는 시간이다.
전체 걸리는 시간이 최소값이라면, 각 유형의 시간 비율은 이미 결정되어 있다. 따라서 최소 소요 시간임이 보장된다면 시나리오나 이동 전략을 변경하여 세 시간 흐름의 순서를 변경하더라도 문제가 발생하지 않는다.
이 순서를 마치 디스크 조각 모음하듯 정리하면 문제를 덜 복잡하게 접근할 수 있다.
사실 그 어떤 경우에도 세 유형 모두 두 개 이상의 조각으로 분리되지는 않는다. 떠나면서 택배를 회수하여 출발 유형이 두 개 이상의 조각으로 분리된다면, 복귀 유형이 한 개 조각이 된다. 반대로 복귀 유형이 두 개 이상의 조각으로 분리된다면, 출발 유형이 한 개 조각이 된다.
문제 풀이
출발 시간과 복귀 시간은 요구하는 소요 시간이 고정되어 있다. 하지만 대기 시간 유형은 고정되어있지 않다.
각 회수 지점에서 물건을 회수할 수 있는 시간은, 출발 시간으로부터 특정한 시간이 지나기만 하면 된다. 다시 말해, 대기 유형은 출발 유형 혹은 회수 유형과 동시에 시간을 소요시킬 수 있다.
따라서 물건 회수는 가능한 한 뒤로 미루는 것이 좋다. 물건 회수를 가능한 한 뒤로 미루는 가장 좋은 방법은 출발 유형을 한 조각으로 제일 앞으로 다 밀어버리는 것이다.
출발을 앞쪽으로 다 밀어버리고, 지점에 따라서는 복귀 시간 중에도 각 지점의 요구 소요 시간을 흐르게 하여, 대기 유형을 최소한으로 줄인다.