문제 링크
(2024/9/10 기준) Gold III

문제 읽기

하노이 탑 변형 문제입니다. 대신 기둥 D가 추가되었고, 기둥 D에 한 번 옮기면 다시 뺄 수 없습니다. 이외에는 기존 하노이 탑과 규칙이 동일합니다. $N$개의 원판을 기둥 D에 옮기는 최소 이동 횟수와, 그러한 이동 방법을 하나 찾아봅시다.

예시

편의를 위해 초기 상태에서의 위로부터 $N$번째 원판을 원판 $N$이라고 하겠습니다. $N=2$일 때,

  1. A에 있는 원판 $1$을 B로 옮긴다.
  2. A에 있는 원판 $2$를 D로 옮긴다.
  3. B에 있는 원판 $1$을 D로 옮긴다.

이렇게 최소 이동 횟수 $3$회로 모든 원판을 기둥 D로 옮길 수 있습니다.

풀이

Base Case

$N=1$인 경우, 바로 기둥 D로 옮기면 최소가 됩니다.
$N=2$인 경우, 위 예시대로 기둥 D로 옮길 수 있고, 사용하는 기둥의 순서가 바뀌어도 이는 이동 횟수는 바뀌지 않으므로, 최소가 됩니다.

Step

$n \geq 3$인 경우, $1$번 원판부터 $N-2$번 원판을 기둥 D를 임의의 기둥으로 옮겨서 $N-2$인 경우를 만들 수 있습니다. (편의를 위해 기둥 C에 옮겼다고 합시다.) 그러면, 기둥 A에는 원판 $N$과 $N-1$이 남게되고, 이 두 원판을 기둥 D로 옮긴 후, 기둥 C에서 기둥 D로 $N-2$개의 원판을 옮기면 됩니다.

만약, 원판 $N$ 하나만 남기고 $1$부터 $N-1$을 옮긴다고 해봅시다. 그렇다면 $N-1$개의 원반을 가지고 반복하고, 더 많은 횟수로 옮겨야 합니다.
또한, 원판을 $3$개 이상 남기려고 하면, 하노이의 탑 규칙을 만족하면서 남은 원판들을 기둥 D로 옮길 수 없습니다. 따라서 $2$개의 원판을 남기고, (단, $N=3$일 때에는 하나밖에 남을 수 없습니다.) 나머지 $N-2$개의 원판을 기존 하노이 탑처럼 옮겨주면 최적해가 됩니다 $_\blacksquare$

코드

use std::{fmt::Write, io::{stdin, Read}, str::SplitWhitespace};

fn main() {
    let mut buf = String::new();
    let mut out = String::new();

    stdin().read_to_string(&mut buf).unwrap();
    let mut scan = Scanner::new(buf.split_whitespace());
    //let tc = scan.next();
    //for _ in 0..tc {
        solve(&mut scan, &mut out);
    //}
    println!("{out}");
}

// overflow, edge case, and 1 based index?
fn solve<'a>(scan: &mut Scanner<'a, SplitWhitespace<'a>>, out: &mut String) {
    let n: usize = scan.next();
    let mut c = 0;
    res(n, 'A', 'B', 'C', out, &mut c);
    println!("{c}");
}

fn res(n: usize, a: char, b: char, c: char, out: &mut String, cnt: &mut usize) {
    if n == 1 {
        writeln!(out, "{a} D").ok();
        *cnt += 1;
        return;
    }
    if n == 2 {
        writeln!(out, "{a} {b}").ok();
        writeln!(out, "{a} D").ok();
        writeln!(out, "{b} D").ok();
        *cnt += 3;
        return;
    }

    hanoi(n - 2, a, c, b, out);
    *cnt += 2_usize.pow(n as u32 - 2) - 1;
    writeln!(out, "{a} {b}").ok();
    writeln!(out, "{a} D").ok();
    writeln!(out, "{b} D").ok();
    *cnt += 3;
    res(n - 2, c, b, a, out, cnt);
}

fn hanoi(n: usize, a: char, b: char, c: char, out: &mut String) {
    if n == 1 {
        writeln!(out, "{a} {b}").ok();
        return;
    }
    hanoi(n - 1, a, c, b, out);
    writeln!(out, "{a} {b}").ok();
    hanoi(n - 1, c, b, a, out);
}

struct Scanner<'a, I: Iterator<Item = &'a str>> {
    iter: I,
}

impl<'a, I: Iterator<Item = &'a str>> Scanner<'a, I> {
    fn new(from: I) -> Self {
        Self { iter: from }
    }
    fn next<T: std::str::FromStr>(&mut self) -> T {
        self.iter.next().unwrap().parse().ok().unwrap()
    }
}

변형 하노이를 해결하는 과정에 일반 하노이의 이동 순서가 필요하므로, 재귀함수를 두 개 만들었습니다.

후기

도널드 커누스의 <구체 수학(Concrete Mathematics)>을 읽어본 적이 있었는데, 여기서 하노이 탑을 심도있게 다뤘습니다. 읽어보길 잘 했네요.