한번 말리니 진짜 끝도 없이 말린다. 솔직히 1번을 이렇게 많이 풀었다는게 좀 놀라울 정도로 어렵게 느꼈는데, 풀이를 보니 문제 이해부터 문제가 있었고.. 아무튼 후회가 많이 남는 대회다.
백준 난이도 나오는 것보고 다이아미만으로는 모두 업솔빙해볼 예정이다.
1. Spiraling Into Control
주어진 달팽이 배열을 따라 중앙으로 이동하려 하는데, 정확히 $k$걸음으로 이동하려한다.
이동 할 때에는 수를 따라 이동하되, 인접한 cell중 더 높은 cell로 이동할 수 있다. 이렇게 순서를 위배해서 더 높은 수로 이동하는 횟수를 최소화 하여 정확히 $k$걸음으로 이동하려 할 때, 횟수를 출력하고, 위배한 걸음에서 이동한 cell pair를 출력하는 문제다.
먼저, 주어진 $k$걸음으로 갈 수 있는지 판별하는 건 어렵지 않다. $k$는 항상 짝수이어야하고,
$n*n - 1$보다 작거나 같아야한다. 간단하게 예제를 손으로 따라가보면 알 수 있다.
계산의 편의를 위해 $k$걸음으로 목적지로 도착해야한다는 조건을 $nn - 1$걸음에서 $k$걸음으로 줄여야한다고 생각해보자. 그럼, 단축경로를 통해서 $nn - 1 - k$걸음을 아껴야한다.
이제, 달팽이배열을 껍질별로 나누어보자. 가장 중앙부터 그 다음 1번째 껍질을 보면 아래에서 중앙으로 단축경로로 이동하면 2만큼 이득이고, 오른쪽에서 중앙으로 이동하면 4만큼 이득, 위에서 중앙으로 이동하면 6만큼 이득이다. (왼쪽에서 중앙으로 이동하면 원래 순서대로 이동한 것과 같으므로 0만큼 이득이다.)
2번째 껍질을 보면 왼쪽에서 중앙방향으로 이동하면 8만큼 이득, 아래에서 중앙방향으로 이동하면 10만큼 이득.... 이런식으로 각 껍질 마다 그리고 방향 마다 이득이 되는 걸음수가 정해져있다. 우리가 이득을 봐야하는 걸음 수는 위에서 구해놓았으므로, 껍질마다 볼 수 있는 이득을 통해 최소한의 단축걸음을 사용하여 이득을 맞추면 된다.
이는 그리디로 가능한데, 각 껍질마다 최대로 아낄 수 있는 걸음부터 확인하여 이득을 빼가면서 check하면 된다. 한가지 걸렸던 점은, 만약 $i$껍질에서 오른쪽에서 단축걸음을 사용하여 $i-1$껍질로 이동했는데, 이 상태에서 위쪽에서 단축걸음을 사용하는게 불가능 하므로 그리디로 안 되는 것 아닌가? 생각했지만 조금만 생각해보면 그리디로 가능하다는 것을 알 수 있다.
만약 위 같은 경우가 더 최적인 경우가 있다고 하면, $i$껍질에서 위쪽에서 단축걸음을 사용하고, $i-1$껍질에서 오른쪽에서 단축걸음을 사용하는 것과 동일하게 걸음을 단축시킬 수 있으므로 그리디가 돌아가는 동안에 걸러질 것이다.
이런식으로 어느 껍질에서, 어느방향으로 이동하는지 알 수 있다면 바로 좌표를 구할 수 있고, 이제 좌표의 배열값을 O(1)에 찾아야한다. 이 부분에서 많이 해맸는데, 차근차근 생각해보면 어렵지않다. 껍질의 시작값을 쉽게 구할 수 있고, 껍질의 시작점의 좌표역시 쉽게 구할 수 있으므로 시작점의 좌표와의 맨하탄 거리를 측정하면 배열의 값을 구할 수 있다.
이렇게 단축걸음으로 이동하기 전의 좌표값과 후의 좌표값을 pair로 넣어두고 출력 해주면 해결된다.
