728x90
문제
유명한 하노이 탑 문제로 1번 탑에서 3번 탑까지 원판의 순서를 유지하면서
옮기기 위한 과정과 이동 횟수를 출력하는 문제다.
접근 방식
재귀를 사용해서 풀 수 있는 교과서 같은 문제로
하노이 탑에 대해서는 잘 알고 있지만 코드로 짜는건 많이 어려웠다.
(재귀가 참 이론은 쉬운데 귀납적으로 생각하고 구현하는 것이 어려운거 같다...)
위에서부터 1번 원판, 2번 원판, ... , n번 원판이라고 했을 때
맨 밑에 있는 n번째 원판을 제외한 모든 원판을 2번 탑으로 옮길 수 있다면
n번 원판을 3번 탑으로 옮길 수 있다는 것이 성립된다.
그 후에 2번째 탑에 있는 원판들을 모두
3번 탑으로 그대로 옮길 수 있다면 하노이 탑의 원리대로
1번 탑의 원판들을 그대로 3번 탑으로 옮길 수 있는 것이다.
그러면 방금 정리한 내용들이 정당한지 확인하면 되는데
n - 1개 일 때는 당연히 원판이 총 두 개니
n - 1번 원판을 2번 탑으로 옮기면 n번 원판을 3번 탑으로 옮길 수 있고
다시 n - 1번 원판을 3번 탑으로 옮기면 그대로 옮길 수 있다는 것을 알 수 있고
이를 이제 코드로 구현하면 된다.
풀이
public class Main {
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
bw.write(((int) Math.pow(2, n) - 1) + "\n");
hanoi(1, 3, n);
bw.write(sb.toString());
bw.flush();
bw.close();
}
private static void hanoi(int start, int target, int n) {
if (n == 1) {
sb.append(start).append(" ").append(target).append("\n");
return;
}
hanoi(start, 6 - start - target, n - 1);
sb.append(start).append(" ").append(target).append("\n");
hanoi(6 - start - target, target, n - 1);
}
'Java > Algorithms' 카테고리의 다른 글
[프로그래머스] 모의고사 (1) | 2023.10.24 |
---|---|
[프로그래머스] 최소직사각형 (1) | 2023.10.24 |
[백준] 1629번 : 곱셈 (1) | 2023.10.13 |
[백준] 11728번 : 배열 합치기 (0) | 2023.10.12 |
[백준] 10026번 : 적록색약 (0) | 2023.10.11 |