마지막으로 점화식에 따라 더 작은 부분 문제를 해결하고, 그 결과로 나온 과정들을 이어 붙여야 합니다. 이는 다음과 같이 작성할 수 있습니다.
private List<int[]> hanoi(int n, int from, int to) {
if (n == 1) return List.of(new int[] {from, to});
int empty = 6 - from - to;
List<int[]> result = new ArrayList<>();
result.addAll(hanoi(n–1, from, empty));
result.addAll(hanoi(1, from, to));
result.addAll(hanoi(n–1, empty, to));
return result;
}
잠깐만요
이렇게 매 부분 문제마다 리스트를 새로 만들고 원소를 이어 붙여 주는 것은 하나의 부분 문제를 해결할 때마다 구해 놓은 모든 과정을 전부 순회해야 하므로 비효율적입니다. 이후에 이를 어떻게 최적화할 수 있는지 살펴볼 것입니다.