8. 28

• Hackerrank <Travel around the world>를 풀었다. DP문제중 좀 더 어려운 걸 풀고 싶어서 Difficult를 골랐는데 갑자기 문제수준이 헬이 됐다-_- 아무리 생각해도 답이 안나와서 Editorial을 참고했는데, 한참 걸려 이해했다.
• 중요한 아이디어는 fuel이 0인 상태로 출발하니까, 어떤 출발점에서 한 번 일주를 할 수 있다면 무한 번 돌고돌 수 있다는 것. 왜냐면 출발점에서 연료가 0인 상태에서 출발해서 일주가 가능했는데, 일주를 한 다음에 출발점에 도착했을 때 연료는 0 이상일 테니까, 일주가 불가능할 리 없다. 또한 어떤 출발점 s에서 시작해 j점에서 막히면, s부터 j점은 모두 불가능한 출발점이 된다. 왜냐면 반대의 논리로.. 도착했을 때 연료가 0이상일 때도 불가능했는데 연료가 0인상태로 출발해 일주가 가능할 리가 없으니까.
• 따라서 출발점을 하나 찾는 것은 쉬운 문제가 된다. 2*N만큼 루프를 돌면서 j에서 막히면 j+1을 다음 후보로 두고 계산하면 된다. 하지만 다른 출발점들을 찾아내는 건 또다른 문제가 된다. 아까같은 후보 제거법을 사용하더라도, 최악의 경우는 여전히 O(N^2)가 된다.
• 여기서 영리한 DP가 필요한데, 하나의 valid 출발점을 알면 DP로 다른 출발점들을 찾아낼 수 있다. 부분문제는 s에서 일주를 하는 데 필요한 최소 도착연료가 need[s]라면, s-1에서 일주를 하는데 필요한 최소 도착연료 need[s-1]를 구하는 것이다. 이런 식으로 s에 대해서 N-1번 수행해주면서, 0이 되는 곳을 세 주면 O(N)만에 풀 수 있다.
• 앞으로 계산할 수 없는 이유는, need[s]로 need[s+1]을 구할 수 없기 때문. s를 거쳐서 s+1로 가면 연료가 남게 되는데, 이는 최소값이 될 수 없다. 반대로 need[s]은 need[s-1]의 정보를 주는데, s-1에서 s까지만 도착하기만 한다면, s이후는 일주가 가능한 경로다. 즉 s-1에서 s까지 가는 데 필요한 연료가 필요한 최소 연료가 된다.
• DP는 자료구조와 점화식을 짜내는 것도 중요하지만, 계산 순서도 못지 않게 중요하다. 이전엔 N부터 반대로 수행해가는 DP를 보았고, 여기서는 확실한 해에서 출발하는 DP라고 할 수 있다. 결국 중요한 것은 하나의 (부분)해에서 단서를 얻어 다른 (부분)해를 찾아내는 것이라고 할 수 있겠다.