BOJ 2494 숫자 맞추기

회전 가능한 숫자 나사 N개가 아래위로 연결 되어 있는데, 숫자 나사는 각각 10개의 면을 가지고 있고 숫자가 0~9까지 순서대로 적혀있다. 왼쪽이나 오른쪽으로 돌릴 수 있는데, 왼쪽으로 돌릴 경우 자신의 밑에 있는 모든 숫자 나사들도 같이 돌아간다. 하지만 오른쪽으로 돌릴 경우 자신만 돌아간다. 이 때 현재 상태와 원하는 상태가 주어지면 원하는 상태로 만들기 위해 최소 몇 칸을 돌려야 하는지, 그리고 어떤 숫자 나사를 몇 칸 움직였는지도 구하는 문제이다.

일단 최소 몇 칸을 돌려야 하는지에 대해 먼저 생각해보자.
처음에는 위에 것을 우선적으로 최대한 많이 돌려야 하나? 우선적으로 어떤 것을 돌리는 게 최소가 될까..? 라든지 .. 좀 찾아보려 했지만 찾지 못했고, 일단 모든 경우를 다 해본다고 하면 각 숫자 나사마다 왼쪽으로 9칸 오른쪽으로 9칸까지... 안 움직이는 경우까지 포함해서 20가지 경우가 있을 것이다. 그런데 숫자 나사의 개수가 최대 10000개 이므로 20의 10000제곱...이 될 것 같다. 아 그리고 왼쪽 오른쪽 둘 다 돌리는 것은...왠지 필요해 보인다...
그럼 10*10 으로 100가지 경우니까 100의 10000제곱...?

일단 dp로 접근해보면 d[n][left][right] = n번 나사를 왼쪽으로 left번, 오른쪽으로 right번 돌리면서 시작하는 경우에 필요한 최소 회전 칸 수
d[n][left][right]=Min( left:0~9, right:0~9) (d[n+1][left][right]) + left+right
그럼 시간 복잡도가 10000 * 10 * 10 * 100 으로... 1억.. 가능은 해 보인다. 

생각만 해서는 문제점을 찾기 힘들다. 구현해 봐야겠다.
구현해 보면서 생각해보니 d[n][num] = n번 나사의 숫자가 num일 때 원하는 상태로 바꾸기 위한 최소 회전 칸 수
이렇게 놓는 것이 나아보인다. 갑자기 확 간단해진 것 같다. 아 그런데, 문제는 n번 나사를 어떻게 돌리냐에 따라 n+1, n+2...이렇게 밑의 나사들도 영향을 받기 때문에 안될 것 같다.

오른쪽으로 돌리는 경우는 상관없지만, 왼쪽으로 돌리는 경우는 아래 나사들에 영향을 준다.
왼쪽으로 돌리면 그 아래 나사들이 같은 칸 만큼 움직인다. 아 그럼 d[n][num][left]로 지금까지 위에서 왼쪽으로 몇 번 움직였는지를 기록하면 될 것 같다. 왼쪽으로 움직이는 것이 누적된 만큼 움직였을 것이고, 또한 왼쪽으로 움직인 것의 누적된 값이 아래에 위치한 숫자 나사들의 상태를 결정하므로 이렇게 하면 될 것 같다.
d[n][num][left]=n번 나사의 숫자가 num이고 ... 가 아니라 n번 나사의 숫자가 무엇인지는 위에서부터 누적된 left만 알면 알 수 있다...
오잉?
그럼 d[n][left]=n번 나사를 돌릴 차례일때 n-1번 나사까지 왼쪽으로 총 left번 돌린 경우에 앞으로 원하는 상태로 바꾸기 위한 최소 회전 칸 수...

d[n][left]
= MIN((leftMove : 0~9, rightMove : 0~9) d[n+1][left+leftMove] ) + leftMove+rightMove
가 되는 것이다

오... 할만하다 역시 생각만 해서는 안된다. 생각만 하지말고 그 생각을 적어봐야 한다. 어느정도 구상이 되면 구현도 해보려고 하고 막히면 다시 생각하되 이렇게 계속 기록하고 적어야 한다. 그래야 생각이 난다.

일단 위의 것을 구현해 봐야겠다. 음 바로 구현하려고 하니까 left가 너무 크다...n이 최대 10000 이기 때문에 누적되면 최대 10만...? 아니 20만도 될 수 있나? 음 고민하다가 문득 떠오른 생각이 아까 풀었던 조세퍼스2 문제의 풀이에서와 좀 비슷한 상황이다. 바로 나사도 조세퍼스 처럼 원형이다! 그렇기 때문에 0~9까지 있는데 왼쪽으로 10번 돌린 것은 0번 돌린 것과 같다. 11번 돌린 것은 1번, 12번은 2번... 그렇다. 바로 누적합%10을 해도 결국은 똑같다.
그러니까 배열의 크기는 d[10000][10]으로 할 수 있다! 오 엄청나다. 아까 조세퍼스2 문제를 복습한답시고 풀지 않았다면 생각 못했을 것 같기도 하다.

일단 구현을 해서 예제에 대한 최소 회전 칸 수는 나온다. 이제 어떤 나사를 어느 방향으로 몇 칸 회전 했는지를 구해야 한다.
음 근데 어느 방향으로 몇 칸 회전했는지를 구하려고 예제도 읽어보고 하는데 아무래도 이 문제에서는 한 쪽으로만 움직여야 하는 것 같다. 나는 구현을 양쪽 방향으로 구현 했는데... 음 그렇다면 좀 수정해야겠다. 이 정도 바꾸는 건 쉬우니.. 그냥 이중 for문을 left, right 따로 계산하도록 for문 2개로 바꿨다.

그리고 어느 방향으로 몇 칸 회전했는지는 최소값이 갱신될 때마다 배열에 넣었다. 이 부분은 쉬웠다. 근데 제출하니까 틀렸다... 고민하던 중 내가 가장 중요한 한 가지를 안넣었다. 바로 이 것은 원형이다. 0에서 9로 넘어가고 9에서 0으로 넘어가는 것을 깜박했다.

음 고쳤는데 고쳐놓고 출력해보니 어느방향으로 몇 칸 회전했는지가 틀리게 나온다. 어느 방향으로 몇 칸 회전했는지를 구할 때 최소값이 갱신될 때마다 배열에 넣는 방식이 틀린 것 같다. 생각해보니 최소인 경우가 여러가지 있을 수 있고 그 경우들이 앞 뒤가 맞게 열결되어야 하기 때문에 그냥 일차원 배열에 넣는 방식으로는 잘못될 것 같다.

결국 그냥 dp를 재귀적으로 구현한 것과 비슷하게 출력하는 것을 구현했고 AC를 받았다.

시간이 12ms로 다른 사람들에 비해 좀 더 걸리는 편이다. 다른 분들의 코드를 보면서 깨달은 것이.. 나처럼 굳이 for문을 써서 모든 경우를 해볼 필요가 없다는 것이다... 왼쪽 몇 칸 오른 쪽 몇 칸이 아니라 그냥 한 번에 왼쪽 또는 오른쪽 둘 중 하나로만 움직여야 하니까 원하는 번호가 되도록 얼마나 움직여야 하는지 계산해서 하면 될 거 같은데...

일단 오른쪽으로 움직이는 것은 최소한으로 움직이는 게 좋다. 그런데 문제는 왼쪽인데, 왼쪽으로 도는 것은.. 아 왼쪽으로 도는 것도 움직이는 것을 최소한으로 하는 게 좋을 것이다. 왜냐하면 어차피 왼쪽으로 최소한으로 움직이든, 한 바퀴 더 돌아서 움직이든 그 아래에 오는 나사들의 위치는 같을 것이기 때문이다. 즉 예를 들어 4에서 5를 만들 때 1칸 움직이는 것이나 11칸 움직이는 것이나 결국 아래 나사들은 똑같이 1칸 움직인 꼴이 된다.

그럼 코드를 좀 수정해 봐야겠다. 수정해서 8ms를 받았다. 4ms도 꽤 많지만, 일단은 이 정도로 해야겠다.
그리고 이 문제는 처음 봤을 때는 어떻게 풀어야 할지 감조차 안 왔는데... 이렇게 내가 생각해서 풀 수 있다는 게 신기하면서도 감격스럽다. 열심히 해야겠다.