[문제풀이] 백준 1914 - 하노이 탑

kodaaa·2022년 12월 1일
0

문제풀이

목록 보기
12/23
post-thumbnail

📢 문제

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. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다.
    2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다.
    3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.

    👉 이걸 이용하면 원반의 크기 생각할 필요 없이 1개의 원반을 옮기는 과정만 출력하면 됨

  • 분할 정복과 비슷한 느낌(프렉탈처럼 같은 규칙의 반복)

  • pow(2, 100)long long으로 저장하려고 했으나 2^100이 훨씬 큼

    • long long : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
    • 2^100 : 126,7650,6002,2822,9401,4967,0320,5376
  • long 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';

처음에 했던 풀이(되는지 안 되는지도 모름)

  • 사람 생각은 앵간하면 안 변하기 때문에... 같은 실수를 반복하지 말자는 의미로 기록
  • 하노이 탑 원리는 1도 생각 안하고, '그저 모든 경우의 수를 재귀로 실행하면 되겠지?' 라는 생각으로 적어본 풀이
#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;
}
  • v를 만든 이유 : 원반의 크기 고려하느라...(더 작은 원반 위에 올릴 수 없으니까)
profile
취뽀하자(●'◡'●)💕

0개의 댓글