자물쇠의 디스크를 돌릴 때, 시계 방향 또는 반시계 방향으로 최대 3칸까지 돌릴 수 있고, 한 번에 최대 3개의 인접한 디스크를 동시에 (시계 방향 또는 반시계 방향으로 최대 3칸까지) 도릴 수 있다.
이 때 N자리의 현재 자물쇠 상태가 주어지고, N자리의 비밀번호가 주어지면, 현재 상태에서 비밀번호를 맞추기 위해 자물쇠를 최소 몇 번 돌려야 하는지 구하는 문제이다.
자물쇠의 첫 디스크 부터 시작해서 각 디스크 마다 인접한 몇 개의 디스크를 1칸, 2칸, 3칸 씩 돌려보는 경우로 다 해봐야겠다고 생각했는데, 질문 게시판 질문과 답변 을 보니 그게 아니었다.
1개 1칸, 인접한 2개 1칸, 인접한 3개 1칸 이렇게 돌리는 경우가 최소일 수 있다.
예를 들어 123 -> 444로 바꾸려면 위와 같이 돌려야 최소 횟수인 3번이 나온다. 그런데 이 것은 디스크 1에서 모두 돌린다는 것을 의미한다.
하지만 나는 처음에 이 것을 디스크 1에서 1칸 돌리고, 디스크 2에서 디스크 2, 1을 묶어서 1칸 돌리고, 디스크 3에서 디스크 3, 2, 1을 묶어서 1칸 돌리면 된다는 식으로 생각했는데, 결국 디스크 1에서 3가지 경우를 다 돌리는 것이나 디스크1, 2, 3에서 각각 한 가지 경우씩 돌리는 것이나 결과는 같지만 dp 배열의 정의를 세우려할 때, 내가 생각한 방법은 멘붕을 겪게 된다...
만약 내가 생각한대로 한다면, 디스크 2에서 돌릴 때와 디스크 3에서 돌릴 때 경우의 수도 많아지지만, 직전 값이, 과거에 계산했던 값이 변하게 될 수 있다. 위의 예대로라면, 디스크3을 돌릴 때, 디스크 1, 2, 값이 변하게 된다. 그럼 그 변한 값이 목표로 하는 비밀번호 값이랑 같은지도 검사해야하고, 이미 비밀번호 값과 같게 해놨다면 변경되면 안되고... 복잡해진다.
디스크 3을 돌릴 때, 디스크 1, 2값은 영향 받지 않으면 편하지 않을까? 디스크 3을 어떻게 돌리든, 디스크 1, 2값은 영향 받지않고 확정돼 있다면 디스크 1, 2를 돌리면서 비밀번호의 디스크 1, 2 값과 같게 해놓고 디스크 3만 신경 쓰면된다. 이렇게 디스크를 하나씩 확정해나가면서 모든 경우를 다 보는 것이 훨씬 편하다.
근데, 디스크 3을 어떻게 돌리든 디스크 1, 2를 신경쓰지 않으려면 디스크 3과 인접한 디스크를 돌릴 때, 디스크 4, 5만 포함해서 돌려야 한다. 즉 디스크1, 2를 동시에 혹은 1, 2, 3을 동시에 돌리는 것은 디스크 1에서만 할 수 있고 디스크 2, 3을 돌리는 것은 디스크 2에서만 할 수 있는 식이다.
그런데 이렇게 하면 정말 모든 경우를 볼 수 있을까? 하는 생각이 들었다.
디스크 3을 돌릴 차례에도 디스크 1, 2를 같이 포함해서 돌려야하지 않을까? 아니다. 왜냐하면 디스크 3에서 인접한 디스크 2와 함께, 즉 디스크2, 3을 돌리는 것이나 디스크 2에서 디스크 2, 3을 돌리는 것이나 효과는 똑같다. 미리 하고 나중에 하고의 차이다. 디스크3에서 디스크 2, 3을 추가로 돌리는 것은 디스크 2에서 디스크 2, 3을 그만큼 미리 더 돌리는 것이나 똑같기 때문에 이렇게 하면 모든 경우를 볼 수 있다.
그리고 헷갈릴 수 있는 것이 돌릴 수 있는 칸의 수가 한 번에 최대 3칸이라고 했는데, 한 번에 3칸이므로 예를들어, 5칸은 못 돌리는 게 아니라, 5칸을 돌리고 싶다면 두 번만에 돌리면 된다.
자, 이제 이해를 했으니 식을 세워보자.
d[n][a][b] : n번 디스크를 비밀번호에 맞추기 위해 돌릴 것이고, n번째(현재) 디스크가 a칸 만큼 돌고, n+1번째 디스크가 b칸 만큼 돌아 있는 상태일 때, 비밀번호로 맞추기 위한 최소 횟수. 답은 d[1][~][~] 중 최소값을 찾으면 될 것이다.-> d[0][0][0]을 구하면 될 것 같다. before[0]==after[0]으로 같고 최소값을 구하는 것이므로 d[0][0][0]을 구하면 d[1][~][~]중 최소값이 구해질 것이다.
식은 d[n][a][b] = MIN( d[n+1][na][nb] + (n번 디스크를 돌린 횟수) ) 가 될 것인데, n번 디스크를 비밀번호에 맞추기 위한 모든 가능한 경우를 다 해봐야하기 때문에 간단하지 않다. 일단 구현을 해봐야 겠다.
d[100][10][10]으로 선언하려고 한다. 왜냐하면, n번째 디스크를 돌릴 때, n번째 디스크는 최대 9번까지 돌려야 한다. 10번을 돌리면 제자리이기 때문에 안 돌리는 것이 낫다. 혹시 10번을 돌리면서 n+1, n+2번째도 같이 돌아가면 최소의 경우가 나오지 않을까 하는 생각을 할 수도 있는데, 전혀 그럴 필요가 없는 것이 n번째 디스크는 가만히 놔두고, n+1번째 디스크 차례가 오면 그 때 돌려버리면 되기 때문이다.
모든 가능한 경우를 해보는 것을 구현하려 하는데, 생각해보니 n번째를 양수만큼(시계방향) 돌릴 것이면 n번째와 인접한 n+1, n+2를 돌릴 때도 양수만큼 돌리면 된다.(음수만큼 돌리는 경우는 해 볼 필요 없다) n번째를 음수만큼 돌릴 것이라면 당연히 나머지도 음수 만큼 돌리면 된다.. 왜냐하면 n번째를 양수만큼 돌리고 인접한 n+1과 n번째를 음수만큼 돌리는 것은 n번째를 그만큼 덜 돌리거나 혹은 음수만큼 돌리거나.. 혹시 필요하다 해도 n+1번째를 볼 때, 음수로 돌려버리면 된다 그러면 결국 횟수는 같다.
그러니까 최소가 나올 가능성이 있는 모든 경우를 보되 최소가 나올 수 없는 경우나 안 봐도 되는 경우는 보지말자는 것이다.
그래서 일단, 시계 방향으로만 돌리는 경우, 반시계 방향으로만 돌리는 경우로 보려고 한다.
구현을 했는데, 몇가지 안되는 경우가 있어서 고민하다가 잘못한 부분을 발견했다. 바로 n번째에서 돌리는 경우, n번째 i번, n+1번째까지 j번, n+2번째까지 k번 돌리기 때문에
n번째는 i+j+k번 돌아가고 n+1번째는 j+k번 돌아가는데, n+1번째가 j+k번 돌아간다는 것을 깜박했다... 일단 그걸 고치니 맞게 나오는데, 제출해 봐야겠다.
와 맞았다!! 다른 사람들에 비해 시간이 좀 더 걸리긴 하지만... 일단 백준님 풀이와, 다른 사람들 풀이 등을 확인해보고 비교해 봐야겠다.
백준님의 코드를 보니, 음수만큼 돌리는 부분을 나처럼 따로 for문으로 처리한 것이 아니라, 양수만큼 돌리는 부분에서 처리하신 것 같다. 좀 더 정확히 말하면 양수만큼 돌리되, 어떻게 돌리든 최소 횟수로 돌리게 처리하셨다. 무슨 말이냐하면 예를 들어 0에서 7으로 돌리려면 7만큼 돌려야 해서 미리 초기화 해놓은 num[7]==3 으로 3번 돌려야한다는 것을 알 수 있는데, 사실은 그렇지 않다. 0에서 음수방향으로 가면 7까지 가는데 3칸만큼 돌려야 해서 1번만 도리면 된다. 그래서 백준님은 num[7]==3이 아닌 num[7]==1로 초기화 해놓으셨다. 그럼 양수만큼 돌리는 경우만 for문으로 해봐도 항상 최소 횟수로 돌리는 경우를 택하게 된다.
그리고 나는 인접한 1개, 2개, 3개를 돌리는 경우를 다 for문으로 해봤는데, 백준님은 인접한 2, 3개만 for문으로 모든 경우를 다 해보시고 1개만 돌리는 경우는 2, 3개를 돌리는 경우에 맞춰서 바로 결정하신다. 2개, 3개를 돌리는 경우는 다른 디스크에 영향을 주기 때문에 모든 경우를 다 해보고 1개만 돌리는 것은 다른 디스크에 영향을 주지 않기 때문에 2개, 3개를 돌린 경우에 따라 목표 번호에 맞게 맞추면 되는 것이다.
지금 다시 짜보면서 깨달은 것은
d[n][a][b]의 의미이다. n번째를 돌릴 것이고, n-1까지의 돌림에 의해서 n번째가 a번, n+1번째가 b번돌아 간 경우 비밀번호로 맞추기 위한 최소 횟수!
참조 : 질문 게시판 질문과 답변 ,백준님 강의 자료 풀이 참조
댓글 없음:
댓글 쓰기