Gidhub BE Developer

[BOJ] 1914. 하노이 탑

2018-09-14
goodGid

Problem

Problem URL : 하노이 탑

Screenshots of Problem Explain

[1] Answer Code (18. 09. 14)

#include<iostream>
#include<cmath>
using namespace std;

char data[100];

// n is cnt
// f is from
// t is to
void hanoi(int n, int f, int t){
    if( n != 0 ){
        /*
         원반이 1,2,3 이라면
         1 + 2 + 3 = 6이고
         
         f : 1
         t : 3이라면
         
         1번 원판에 가장 아래를 제외하고
         나머지 원판들은 2(= 6-1-3 )로 가야한다.
         */
        hanoi(n-1, f, 6-f-t );
        printf("%d %d\n",f,t);
        hanoi(n-1, 6-f-t, t);
    }
}

int main(){
    int n;
    scanf("%d",&n);
    
    data[0]='1';
    int cnt = 0;
    /*
     [1] or [2] 둘 다 사용 가능
     [3]에서 초기화 해줄 때
     data 변수의 타입이 char이기 때문에
     ASCII 값을 넣어도 어차피 char형
     char 형을 넣어도 어차피 char형이다.
     */
    int ctmp; // [1]
//    char ctmp; // [2]
    for(int i=1; i<=n; i++){
        int tmp=0;
        for(int j=cnt; j>=0; j--){
            /*
             *2 : 2제곱
             *3 : 3제곱
             *n : n제곱
             */
            tmp += ( data[j]-'0' ) * 2;
            data[j] = tmp % 10 + '0';
            tmp /= 10;
        }
        
        if(tmp>0){
            ctmp = tmp + '0';
            cnt++;
            for(int j=cnt; j>=1; j--){
                data[j] = data[j-1];
            }
            data[0] = ctmp; // [3]
        }
    }
    
    data[cnt]--;
    printf("%s\n",data);
    
    if( n<=20 )
        hanoi(n, 1, 3);
    
    return 0;
}

Review

  • 이동 횟수를 1 « n - 1 공식으로 하려면 2^100 - 1은 표현이 불가능하다..

  • 그래서 문자열로 이동 횟수를 처리해줘야 하는데 그 부분이 어려웠다.

  • 그래도 중요한 코드이기에 Key Point로 정리해놨다.


Comments

Content