[C++] BOJ11729 {Recursive} (Tower of Hanoi)

[Settpark]

수학적 귀납법에 대한 정의

1. a = k일때 성립함을 가정
2. a = k+1일때 도 성립함을 증명
3. 2,3의 결과로 모든 경우에 대해 성립함을 증명하는 방법

hanoi에 적용

1. 1개의 원판을 a에서 b로 옮길 수 있다 // base condition
2. n-1개의 원판을 a부터 원하는 곳으로 옮길 수 있다. // 가정
3. n개의 원판을 a부터 원하는 곳으로 옮길 수 있다. // 성립

void BOJ11729::hanoi(int a, int b, int n) { // n개의 원판을 원하는 곳으로 옮긴다.
    if (n == 1) {  // base condition;
        cout << a << ' ' << b << '\n';
        return;
    }
    hanoi(a, 6-a-b, n-1); // n-1개를 빈곳으로 옮긴다.
    cout << a << ' ' << b << '\n';
    hanoi(6-a-b, b, n-1); // 빈 곳에서 목적지로 n-1개를 옮긴다.
}

아직 아리송하지만 오늘은 어제에 비해 좀 많이 이해했다.