[BOJ] 23250: 하노이 탑 K

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

 

 

 

우선 하노이탑을 해결하는 방법에는 여러가지 방법이 있다.

 

Iterative Solution,

Recursive Solution,

Binary Solution.

 

보통 대부분 이 문제를 Recursive Solution의 형태로 푸는 것 같다.

재귀함수를 통해 이동을 구하는 형태.

 

하지만 다른 방법들도 존재한다.

 

기둥이 3개인 하노이탑에서는 원반의 개수만 안다면 각 순서에 원반이 어디로 움직여야 하는지를 결정할 수 있다.

왜냐하면 원반의 개수가 짝수라면 가장 작은 원반과 큰 원반은 서로 다른 방향으로 움직여야 하고, 원반의 개수가 홀수라면 서로 같은 방향으로 움직여야 하노이탑이 해결되기 때문이다.

이를 조금 더 정리하면 원반에 부여된 번호의 짝홀성을 이용해서 다음에 갈 기둥을 결정할 수 있다는 것이다.

 

그렇다면 움직일 원반은 어떻게 결정할 수 있을까?

이는 m번째 움직임이라고 했을 때, (m이 2로 나누어지는 횟수 +1) 의 번호를 가진 원반이라고 결정할 수 있다.

 

 

이 Iterative Solution을 조금 더 단순화시켜서 압축시킨 내용이 Binary Solution이다.

 

잘 생각해보며 (m이 2로 나누어지는 횟수+1) 라는 것은 m을 이진수로 표현했을 때, 오른쪽으로부터 세었을 때 (0의 개수 + 1)이기도 하다.

또한 위에서 생각했던 짝홀성을 이용한 원반의 움직임 결정을 비트 연산자를 통해 단순화시키면

((m & (m-1)) % 3 +1) 번째 기둥에서 (((m|(m-1))+1)%3 + 1) 번째 기둥으로 이동하면 된다는 수식이 나오게 된다.

 

하지만 이 수식에서 주의해야 할 점은 이 수식은 항상 모든 하노이탑이 다른 기둥으로 전부 이동하는 것은 보장하지만, 그 최종 종착지가 3번 기둥이라는 보장이 없다는 것이다.

그게 2번 기둥이 될 수도 있다는 것이다.

그래서 3번 기둥임을 보장하기 위해서는 원반의 개수가 홀수일 때에는 그대로 저 수식을 사용해도 되지만, 짝수일 때에는 저 수식에서 결과가 2가 나왔다면 3으로, 3이 나왔다면 2로 바꾸어 주어야 한다.

 

이것이 이진수의 특징과 비트 연산을 활용한 Binary Solution이다.

 

그렇다면 이것을 코드로 구현하면 어떻게 될까?

 

코드 (C++)

#include <iostream>

using namespace std;

int main() {
    long long N, K;
    cin >> N >> K;

    long long A = ((K & (K - 1)) % 3) + 1;
    long long B = (((K | (K - 1)) + 1) % 3) + 1;

    if (N % 2 == 0) {
        if (A == 2) A = 3;
        else if (A == 3) A = 2;
        
        if (B == 2) B = 3;
        else if (B == 3) B = 2;
    }

    cout << A << " " << B;
}

 

이렇게 된다.

 

 

이러한 방식으로 해결하게 되면, 재귀함수가 아닌 단순한 비트 연산만으로 해결하기 때문에 재귀함수를 사용하여 해결한 다른 사람들보다 훨씬 짧은 코드로 해결이 가능하다.

 

그래서 나는 python으로 golfscript를 이길 수 있을지 궁금해져서 python으로 숏코딩을 도전해보았다.

 

N,K=map(int,input().split())
M=[1,3,2,3]
A,B=(K&(K-1))%3,((K|(K-1))+1)%3
A,B=M[(A>0)*(A+N%2)],M[(B>0)*(B+N%2)]
print(A,B)

처음에는 if문이 아닌, 배열을 통해 코드를 줄여보았다.

 

N,K=map(int,input().split())
f=lambda x: [1,3,2,3][(x>0)*(x+N%2)]
print(f((K&(K-1))%3),f(((K|(K-1))+1)%3))

이후 반복되는 부분을 람다를 이용해서 줄여 보았고

 

N,K=map(int,input().split())
f=lambda x: [1,3,2,3][(x>0)*(x+N%2)]
print(f((K&~-K)%3),f(((K|~-K)+1)%3))

(k-1)을 더 짧은 ~-k로 바꾸었다.

기존에는 연산자 우선순위 문제로 괄호를 없애지 못했지만, 이렇게 바꾸게 되면 연산자 우선순위가 ~가 더 높기 때문에 괄호 생략이 가능해진다.

 

N,K=map(int,input().split());print(*map(lambda x:[1,3,2,3][(x>0)*(x+N%2)],[(K&~-K)%3,((K|~-K)+1)%3]))

map을 써서 줄여보기도 하고

 

N,K=map(int,input().split());print(*(1+(x>0)*(1+(x!=2-N%2))for x in[(K&~-K)%3,((K|~-K)+1)%3]))

x = 1, 2, 3, 4에 대해서만 값이 각각 1, 3, 2, 3이 나오는 엄청난 수식을 우연히 만들어내서 배열보다 짧게 만들어보기도 했다.

또한 map이 아닌 배열과 for문을 이용해서 lambda 라는 기호를 없앰으로써 길이를 줄였다.

 

N,K=map(int,input().split());print(*('1323'[(x>0)*(x+N%2)]for x in[(K&~-K)%3,((K|~-K)+1)%3]))

마지막으로 배열이 아니라 문자열로 하면 ,를 없앨 수 있어서 이를 통해 길이를 줄였다.

 

이렇게 줄인 코드의 길이가 93B이다.

 

하지만 이렇게 했는데도, 74B로 짠 친구의 친구의 기록을 이기지 못했다.

심지어 다른 친구는 71B로도 성공해버렸다 ㅋㅋ

 

 

숏코딩 4등이었는데 친구들한테 밀려서 6등이 된 모습

 

 

그래도 다양한 방법을 생각해볼 수 있었어서 재밌었던 것 같다.