[Boj] 백준 C++ #1914 하노이탑

작성자	김명원
일 시	2024. 11. 26 (화) 18:00 ~ 21:00
장 소	미래관 429호 자율주행스튜디오
참가자 명단	임혜진,  장원준, 이재영, 성창민, 김명원
사 진

 

📍 문제링크 : https://www.acmicpc.net/problem/1914

 

📍 알고리즘 분류 : 재귀

 

📍 문제 풀이 : 알고리즘 시간에 배운 내용과 코드를 기반으로 하노이탑 문제를 풀었다. 옮긴 횟수를 출력하는 것 때문에 시간이 오래 걸렸다. 처음에는 재귀함수가 호출될 때마다 카운트를 해가며 구했는데, N<=20인 경우에는 옮긴 횟수를 출력 후, 수행 과정을 출력해야하므로 옮긴 횟수를 더 먼저 구할 수 있어야 했다. 고민하면서 질문 게시판을 봤는데 다들 카운트가 아닌, 2^n -1로 수행횟수를 구했다. 생각해보니 일반항을 구할 수 있었다.하지만 N이 너무 커질 경우 지수 표기법으로 표기되는 것이 또 문제였는데, string으로 변환 후 소수점 자리를 찾아 잘라주어야 했다. 핵심 알고리즘은 구현했는데 출력 형태를 맞추느라 시간 걸리고 헤매는게 참 별루다.

 

📍 코드 :

#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;

void Hanoi(int n, int a, int b, int c){
    if(n>0){
        Hanoi(n-1, a, c, b);
        cout<<a<<" "<<c<<'\n';
        Hanoi(n-1, b, a, c);
    }
}

int main() {
    int N; cin>>N;
    
    string tmp = to_string(pow(2,N)); // 결과값 double을 string으로 변환하여 저장
    int dot = tmp.find('.'); // 소수점(.)이 있는 위치를 반환하여 저장
    tmp = tmp.substr(0,dot); // 소수점부터 그 이후는 잘라냄. 소수점 이전의 정수 부분만을 남김
    tmp[tmp.length() - 1] -= 1; // 마지막 문자(char)를 1 감소시킴. 아스키 코드를 1 감소하는 방식.
    cout<<tmp<<'\n';

    if(N<=20){
        Hanoi(N,1,2,3);
    }
    return 0;
}

 

 

재귀함수를 잘 사용할 수 있는 대표적인 문제 하노이탑을 풀었다.
실제 개발을 할 때 재귀함수에 익숙치 않아 잘 사용하지 않았는데 앞으로 많이 사용해 봐야겠다.