프로젝트 오일러 122번

The most naive way of computing \(n^{15}\) requires fourteen multiplications:

\[ n \times n \times \cdots \times n = n^{15}\] But using a "binary" method you can compute it is six multiplications:

\[\begin{split} n \times n &= n^2 \\ n^2 \times n^2 &= n^4  \\ n^4 \times n^4 &= n^8 \\ n^8 \times n^4 &= n^{12} \\ n^{12} \times n^2 &= n^{14} \\ n^{14} \times n &= n^{15} \end{split}\]However it is yet possible to compute it in only five multiplications:

\[\begin{split} n \times n &= n^2 \\ n^2 \times n &= n^3 \\ n^3 \times n^3 &= n^6 \\ n^6 \times n^6 &= n^{12} \\ n^{12} \times n^3 &= n^{15} \end{split}\] We shall define \(m(k)\) to be the minimum number of multiplications to compute \(n^k\); for example \(m(15)=5\).

For \(1 \le k \le 200\), find \(\sum m(k)\).

---

\(n\) 들을 곱하여 \(n^{15}\) 을 만드는 가장 우직한 방법은 14 번의 곱셈을 수행하는 것이다. \[ n \times n \times \cdots \times n = n^{15}\] 그렇지만 다음과 같은 방법을 이용한다면 여섯 번의 곱셈만으로 \(n^{15}\) 을 얻을 수 있다.\[\begin{split} n \times n &= n^2 \\ n^2 \times n^2 &= n^4  \\ n^4 \times n^4 &= n^8 \\ n^8 \times n^4 &= n^{12} \\ n^{12} \times n^2 &= n^{14} \\ n^{14} \times n &= n^{15} \end{split}\] 하지만 다음과 같이 한다면 다섯 번의 곱셈만으로도 \(n^{15}\) 을 얻는게 가능하다. \[\begin{split} n \times n &= n^2 \\ n^2 \times n &= n^3 \\ n^3 \times n^3 &= n^6 \\ n^6 \times n^6 &= n^{12} \\ n^{12} \times n^3 &= n^{15} \end{split}\] \(m(k)\) 를 \(n^k\) 을 얻기위해 필요한 곱셈의 최솟값으로 정의하자. 예를 들어, \(m(15)=5\) 가 된다. \(\sum \limits_{k=1}^{200} m(k)\) 를 구하시오.

이 문제를 풀기 위해서 정말 별 짓을 다 해봤다. 혼자서 난 천잰가봐 하며 여러 가지 아이디어를 냈었지만, 몇 가지 소수에서 규칙성이 성립하지 않아 오답을 만들어 낼 뿐이었다. 오답 생산 3일째가 되던 날, 스스로 둔재임을 인정할 수 밖에 없었다. 도저히 안되겠다 싶어 구글링을 해서 "Addition chain" 이라는 위키피디아 글을 보게 되었다. 놀랍게도 거기에서 아직까지 이 문제를 풀기 위한 나이스한 알고리즘이 없다는 것을 확인하게 되었고, 스스로 범재임을 각인시키며 위로할 수 있었다.

결국 이문제는 모든 가능한 경우들을 전부 조시하면서 답을 찾을 수 밖에 없었다.

  

path = [[list(range(1, i+1))] for i in range(201)]
for i in range(1, len(path)):
    for j in path[i]:
        for k in j: 
            if i + k < len(path):
                if len(path[i][0]) + 1 < len(path[i + k][0]):
                    path[i + k] = [j + [i + k]]
                elif len(path[i][0]) + 1 == len(path[i + k][0]):
                    if j + [i + k] not in path[i + k]:
                        path[i + k].append(j + [i + k])
print(sum(len(p[0]) - 1 for p in path[1:]))

대충의 방법을 살펴보면 다음과 같다. 편의상 1부터 5까지만을 대상으로 방법을 살펴보자.  

일단 1부터 5까지 다음과 같은 리스트를 만든다.

[[1]]

[[1, 2]]

[[1, 2, 3]]

[[1, 2, 3, 4]]

[[1, 2, 3, 4, 5]]

이렇게 하는 이유는 문제에서 예로 보여준 \(n \times n \times \cdots \times n = n^{15}\) 처럼 \(n\) 을 하나씩 곱해가면서 목표한 거듭제곱을 만들 수 있기 때문이다. 이후에 더 간단하게 목표한 거듭제곱에 도달할 경우 리스트를 업데이트 해 나갈 것이다.

제일 먼저 [1] 을 대상으로 [1]의 길이(length)에 1을 더해 본다. 그리고 1+1이 두 번째 [1, 2]의 길이와 같기 때문에 [1]에 [1+1] 을 더한 [1, 2] 를 만들어 낸다. 그런데 이미 [1, 2] 가 두 번째 리스트에 속해 있기 때문에 루프를 계속 이어 나간다.

두 번째로는 [1, 2]를 대상으로 2+1 (마지막 항에 첫 번째 항을 더하는 것이다.) 결과로 3이 나오는데, [1, 2]의 길이에 1을 더한 값 3이 세 번째 리스트의 [1, 2, 3]의 길이와 같으므로 [1, 2] 에 [1+2] 를 더한 [1, 2, 3]을 만든다. 그렇지만 이것이 세 번째 리스트에 이미 있으므로 루프를 계속 진행한다. 그 다음 2+2 (마지막 항에 두 번째 항을 더하는 것이다. 여기서는 마지막 항이 두 번째 항이 된다.) 결과로 4가 나오는 것을 확인한다. [1, 2]의 길이에 1을 더한 값 3이 네 번째 리스트의 [1, 2, 3, 4]의 길이보다 작기 때문에 네 번째 리스트를 [1, 2, 2+2] 즉, [1, 2, 4]로 업데이트 한다. 이렇게 하면 다음과 같이 리스트들이 업데이트 된다.

[[1]]

[[1, 2]]

[[1, 2, 3]]

[[1, 2, 4]]

[[1, 2, 3, 4, 5]]

이제 세 번째 [1, 2, 3]을 대상으로 3+1(마지막 항에 첫 번째 항을 더하는 것이다)을 해 보고 그 결과가 4임을 확인한다. [1, 2, 3]의 길이에 1을 더한 4가 네 번째 리스트의 [1, 2, 4] 보다 크기 때문에 루프를 계속 진행한다. 다음으로 3+2(마지막항에 두 번째 항을 더한다)가 5임을 확인한다. [1, 2, 3]의 길이에 1을 더한 값이 다섯 번째 리스트의 [1, 2, 3, 4, 5]의 길이보다 작으므로 다섯 번째 리스트를 [1, 2, 3, 5] 로 업데이트 한다. 그 다음은 3+3 (마지막 항에 세 번째 항을 더한다)이 6이 되지만 우리는 5까지만을 대상으로 하기 때문에 아무일도 하지 않는다. 이렇게 되면 다음과 같이 리스트가 업데이트 된다.

[[1]]

[[1, 2]]

[[1, 2, 3]]

[[1, 2, 4]]

[[1, 2, 3, 5]]

이제 네 번째 [1, 2, 4] 를 대상으로 위와 같은 과정을 반복한다. 4+1은 5가 되는데, [1, 2, 4]의 길이에 1을 더한 값이 [1, 2, 3, 5]의 길이와 같으므로 [1, 2, 4 + 4+1] 즉 [1, 2, 4, 5]를 만들어 내고, 이 리스트가 다섯 번째 리스트에 포함되지 않으므로 다섯 번째 리스트에 [1, 2, 4, 5]를 추가한다. 4+2, 4+4 는 대상의 범위를 넘어서므로 (5보다 크므로) 패스한다. 이렇게 하면 다음과 같이 리스트들이 업데이트 된다.

[[1]]

[[1, 2]]

[[1, 2, 3]]

[[1, 2, 4]]

[[1, 2, 3, 5], [1, 2, 4, 5]]

이로써 원하는 답을 얻어낼 수 있다. 1은 0번, 2는 1번, 3 과 4는 2번, 5는 3번의 곱셈으로 목표에 도달 할 수 있게 된다. 

정말 대충 설명을 하긴 하였지만, 내가 다시 읽어봐도 무슨 말인지 잘 모르겠다. ㅋㅋ