PS 이야기

인접한 도시 사이를 이동하는데 걸리는 시간 1, 한 도시에 있는 관광지를 모두 둘러보는 시간 1이 걸리고 시작점이 주어졌을 때, 가장 관광지를 많이 방문하는 문제다. 물론 같은 관광지를 여러 번 방문해서는 안된다. 답이 될 수 있는 이동 경로는 아래 두 가지 중 하나이다. 1) 시작점에서 왼쪽으로 0칸 이상 가다가 어느 순간 오른쪽으로 이동하여, 시작점 보다 오른쪽으로 간다. 2) 시작점에서 오른쪽으로 0칸 이상 가다가 어느 순간 왼쪽으로 이동하여, 시작점 보다 왼쪽으로 간다. 즉, 쉽게 말하자면 방향을 한 번만 바꾼다는 것이다. 두 번 이상 방향을 바꾸어 왔다갔다 하는 것은 이동하는 시간만 늘리므로 항상 안좋다는 것을 알 수 있다. 2번 경우는 전체를 좌우로 뒤집었을 때 1번 경우와 같아지므로, 1번 ..