백준 1914 하노이탑 / C++

문제 : 1914

풀이 point

백준 하노이탑 이동순서11729번을 참고하여 구현한다.
단 N이 20이 넘는 경우 $2^N-1$값만 출력해야하지만 n=100이 최대이기 때문에 long long의 범위를 한참 넘기 때문에 다른 방법이 필요하다.

풀이 방법

그럼 어떻게 해야하는가… 파이썬이라면 그냥 해도 되지만 C++은 다른 방법이 필요하다.
cmath 라이브러리에 있는 pow함수를 통해 n제곱 연산을 할수 있지만 부동소수 계산이므로 오차가 발생할 수 있다.
하지만 여기선 소수점 밑은 그냥 날려주면 된다. pow를 통해 연산을 한 후 스트링으로 타입 변환을 해준다.
.을 찾은 후 소수점 밑은 날려버린 뒤 -1을 해주면 된다!

코드

//백즌 1914, 하노이 탑

#include <iostream>
#include <cmath>

void recur(int n, int a, int b){
    if(n == 1){
        std::cout << a << ' ' << b << '\n';
        return;
    }
    
    recur(n-1, a, 6-a-b);
    std::cout << a << ' ' << b << '\n';
    recur(n-1, 6-a-b, b);
}

int main (){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N;
    std::cin >> N;
    std::string s = std::to_string(pow(2, N));
	
	int x = s.find('.');	
	s = s.substr(0, x);	
	s[s.length() - 1] -= 1;	        
    
    std::cout << s << "\n";
    if(N <= 20) recur(N, 1, 3);
    return 0;
}

2025-02-13T01:21:48.613Z