#1914 하노이 탑

# 문제

# 입력 및 출력

# 풀이

저번에 하노이 탑 문제를 풀었을 땐 하노이탑 유형 자체를 이해하기 위해 다른 사람 블로그를 참고해서 풀었었는데

이번엔 혼자 풀어보기 위해 안보고 풀어봤다

 

하노이탑 자체는 매우 쉬운데 이 문제에서 어려웠던 부분은 옮긴횟수 k를 구하는 부분이다

비트 연산자를 사용하려고 했는데 long long 이라도 64비트밖에 표현이 안돼서

N이 특정 수 이상 넘어가면 비트가 잘려서 출력이 됐다

 

옮긴횟수 k = 2^n - 1

그래서 string을 사용하려고 했다

cmath헤더의 pow함수를 사용해서 2^n을 구하고 이것을 string으로 바꿔주었다

pow는 실수형을 리턴하기 때문에 뒤에 필요없는 소수점이 존재한다

따라서 소수점 부분을 잘라주기 위해 string 헤더의 find함수와 strsub함수를 사용했다 

그리고 마지막 -1을 해줬다

 

여기서 헷갈렸던 점이 string을 인덱스로 접근하면 char형인데 -1을 해주는게 맞는가 싶었다

'1'의 아스키 코드 값을 빼줘야하는거 아닌가 싶었는데

결과도 아스키코드 값이기 때문에 -1만 해줘도 제대로 된 계산이 된다

예) '3' - 1 = '2'

 

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

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	string s = to_string(pow(2, n));
	s = s.substr(0, s.find('.'));
	cout << s << "\n";
	if (n <= 20) hanoi(1, 2, 3, n);
}

 

처음에 -1을 안해줘서 한번 틀렸다ㅋㅋ

 

전에 풀었던 문제랑 다른게 없어 보였는데 정수형 변수 범위 초과 때문에 풀다 보니 꽤 오래걸렸다