문제에서 요구하는 수식을 구하기 위해서 아래와 같은 식을 세울 수 있다.
f(n) = f(n-1) + n^n
여기서 재귀와 메모아이제이션이 생각났다. 이 방법이 __solution() 이다. 그러나 이 방법은
최대 백만번에 재귀 함수 호출로 인해 스택 오버플로우 문제가 발생하여 사용하지 못했다.
그래서 매모아이제이션을 유지하면서 재귀 대신 반복문으로 진행하였다.
여기서 단순한 방법으로 n^n을 구하면 아마 타임아웃 문제가 발생할 것 같아서 좀 더 효율적으로
n^n을 구해야 한다.
임의의 짝수는 2의 거듭제곱 들의 합으로 구성되며 홀수는 여기에 "1" 만 더한 것이다.
15 = 1 + 2 + 4 + 8 이므로
15^15 = 15^(1 + 2 + 4 + 8) = 15^1 * 15^2 * 15^4 * 15^8 이다.
더욱이 15^4 은 앞서 구한 15^2 * 15^2 이므로 이전에 사용한 값을 재활용 할 수 있다.
또, 백만은 이진수로 0000 0000 0000 1111 0100 0010 0100 0000 이므로
[0:31] 을 모두 체크하지 않아도 된다.