[BOJ] 4243번: Security

https://www.acmicpc.net/problem/4243

뭔가 다이나믹같긴 한데 D를 잡기가 좀 어려웠습니다. 맨 처음엔 D[i][j][dir]를 (i to j)를 순찰하는데 걸리는 최소 latency(dir는 끝나는 곳을 의미. 0이면 왼쪽, 1이면 오른쪽)으로 뒀는데, latency가 높더라도 total time이 작은게 다음 DP에 도움이 될 수도 있어서 D를 어떻게 잡아야하나 고민하다가 D[i][j][dir]를 (i to j)까지 이미 순찰했다고 할 때, 나머지를 순찰하는데 걸리는 최소 latency로 두었습니다. 이러면 깔끔하게 식이 세워집니다. D의 순서를 고려하는게 귀찮아 memoization으로 해결했습니다.

https://github.com/blisstoner/BOJ/blob/master/4243.cpp