프로그래머스 - 하노이의 탑

문제 링크

제출 코드(통과)

using System;

public class Solution {
    public int[,] solution(int n)
    {
        var size = Power(2, n) - 1;
        var answer = new int[size, 2];
        Iter(n, 0, 1, 3, answer);
        return answer;
    }

    private static int Power(int baseNum, int exp)
    {
        var result = 1;
        for (var i = 0; i < exp; i++)
            result *= baseNum;
        return result;
    }
    
    private int Iter(int n, int step, int from, int to, int[,] answer)
    {
        if (n == 1)
        {
            answer[step, 0] = from;
            answer[step, 1] = to;
            return step + 1;
        }

        var nextTo = 6 - from - to;
        var next = Iter(n - 1, step, from, nextTo, answer);
        answer[next, 0] = from;
        answer[next, 1] = to;
        next++;
        return Iter(n-1, next, nextTo, to, answer);
    }
}

전형적인 재귀 문제 중 하나인 하노이 탑이다. 총 시행 횟수의 점화식이 x(n+1) = 2x(n) + 1이므로 일반항은 x(n) = 2^n - 1이다. 크기부터 계산해 전체 배열을 한 번 할당하고, 내부를 채워나가는 방식으로 작성했다.