https://www.acmicpc.net/problem/1914
재귀
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int N = 0; //원판 개수
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()
{
cin >> N;
string s = to_string(pow(2, N)); // pow(2,100)은 long long보다도 큰 값이므로 문자열로 저장해야 함
int pos = s.find('.'); // s에서 소수점 .의 위치(인덱스) 찾기
s = s.substr(0, pos); // s에서 인덱스 0~pos까지만 추출
s[s.length() - 1] -= 1; // 2^N-1이 답이므로, 문자열의 마지막 인덱스 값에 -1 해줌 : 숫자문자-1 해도 아스키코드값-1이니까 숫자-1한 거랑 같아짐
cout << s << '\n';
if (N <= 20)
{
hanoi(N, 1, 2, 3);
}
}
💡 하노이의 탑의 기본 원리
👉 이걸 이용하면 원반의 크기 생각할 필요 없이 1개의 원반을 옮기는 과정만 출력하면 됨
분할 정복과 비슷한 느낌(프렉탈처럼 같은 규칙의 반복)
pow(2, 100)
을 long long
으로 저장하려고 했으나 2^100
이 훨씬 큼
long long
: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,8072^100
: 126,7650,6002,2822,9401,4967,0320,5376long long 보다 큰 값을 출력해야 할 때 : 문자열로 변환해서 출력
string s = to_string(pow(2, N)); // pow(2,100)은 long long보다도 큰 값이므로 문자열로 저장해야 함
int pos = s.find('.'); // s에서 소수점 .의 위치(인덱스) 찾기
s = s.substr(0, pos); // s에서 인덱스 0~pos까지만 추출
s[s.length() - 1] -= 1; // 2^N-1이 답이므로, 문자열의 마지막 인덱스 값에 -1 해줌 : 숫자문자-1 해도 아스키코드값-1이니까 숫자-1한 거랑 같아짐
cout << s << '\n';
2^100
은 실수이므로 정수 부분만 떼어냄#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int minCnt = INT_MAX; //최소 이동수
int N = 0; //원판 개수
void hanoi(int cnt, vector<vector<int>> v, int ex, int now) // v : 값에 의한 호출(call by value)
{
//원판 이동
// v[ex].back() => v[now].back()
int tmp = v[ex].back();
v[ex].pop_back();
v[now].emplace_back(tmp);
// 3번째 위치로 모두 이동하면
if (v[now].size() == N)
{
minCnt = min(minCnt, cnt);
return;
}
for (int i = 0; i < 3; i++)
{
// 1. 이전 위치와 달라야함
// 2. 현재 위치와 달라야함
// 3. 현재 위치의 가장 위 원판보다 수가 크거나, 아무 원판도 없어야 함
if (ex != i && now != i && (v[i].back() > v[now].back() || v[i].size() == 0))
{
//원판 이동 함수 호출
hanoi(cnt + 1, v, now, i);
}
}
}
int main()
{
cin >> N;
//초기 원판 셋팅
vector<vector<int>> v(3, vector<int>());
v[0].resize(N);
for (int i = N; i > 0; i--)
{
v[0][N - i] = i;
}
hanoi(0, v, 0, 1);
hanoi(0, v, 0, 2);
cout << minCnt;
}