[백준 1914번 C++] 하노이 탑

1914번: 하노이 탑 (acmicpc.net)

1914번: 하노이 탑

---

C++ 백준 11729 (하노이 탑 이동순서) (seongmok.com)

C++ 백준 11729 (하노이 탑 이동순서)

[C언어/C++] pow, sqrt 함수에 대해서(루트함수, 제곱, 제곱근) (tistory.com)

[C언어/C++] pow, sqrt 함수에 대해서(루트함수, 제곱, 제곱근)

 2의 n 승을 연산하고 싶을 때 

1. cmath 헤더파일 불러와서 pow() 메서드 이용 - pow는 float로 출력함
#include <cmath>
(int)pow(2,n) - 1; 

2. 시프트 연산
(1<<n) - 1;

그렇게 기본적인 하노이 코드를 완성했는 데 

틀렸다

문제의 코드

#include <iostream>
#include <cmath>

using namespace std;

void hanoi(int n, int start, int mid, int end){
    if(n == 1) {
        cout << start << " " << end << "\n";
        return;
    }
    hanoi(n-1, start, end, mid);
    cout << start << " " << end << "\n";
    hanoi(n-1, mid, start, end);
    
}

int main()
{
    int n;
    cin >> n;
    
    cout << (int)pow(2,n) - 1 << "\n";
    
    if(n <= 20) hanoi(n, 1, 2 , 3);
    return 0;
}

백준 1914번 : 하노이 탑 c++ — 나의 개발일지 (tistory.com)

백준 1914번 : 하노이 탑 c++

검색해보니 n이 100까지 가서 너무 큰 수가 출력 되므로 string으로 변환해서 해줬어야 했던 것

전에도 이런 문제 있었는 데!

 

하노이탑 과정은 안건드려도 되고, 최소 이동 과정만 변형 해줘도 됐다.

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

void hanoi(int n, int start, int mid, int end){
    if(n == 1) {
        cout << start << " " << end << "\n";
        return;
    }
    hanoi(n-1, start, end, mid);
    cout << start << " " << end << "\n";
    hanoi(n-1, mid, start, end);
    
}

int main()
{
    int n;
    cin >> n;
    
    string a = to_string(pow(2, n));
	
	int x = a.find('.');				//pow 함수 결과가 실수형이기에 소수점 찾기
	a = a.substr(0, x);				//소수점 앞자리만 나오게하기
	a[a.length() - 1] -= 1;	        
    
    cout << a << "\n";
    
    if(n <= 20) hanoi(n, 1, 2 , 3);
    return 0;
}

++ 스터디 호롤ㄹ로로 씨가 보내주신 좋은 설명 링크

무조건 이해시켜 드립니다. 비법 대방출! 재귀 알고리즘 Recursion - 하노이탑, 피보나치 수열 - YouTube