1~n개의 숫자를 모두 더한다. n(n+1)/2
이웃한 수를 더하는 과정이 있기에 1~n까지 모든 수는 두 번씩 사용된다. x2 n(n+1)
이웃한 수를 더한 값은 총 n개 제곱수의 갯수는 n개 대충 49까지 쓰인다고 생각하면
1*1a+2*2b+...+7*7g=n(n+1)과 a+b+...+g=n를 동시에 만족하는 값을 찾으면 되나?
여기서 어떻게 함?
그래프로 접근하면 됨.
각각 1~n까지의 인덱스를 가진 n개의 정점으로 이루어진 무향 그래프가 있고,
두 정점의 인덱스 합이 제곱수인 경우, 그 두 정점을 잇는 간선이 정확히 1개 존재한다고 해보자
그러면 위 문제는 만들어진 무향 그래프에서 해밀턴 회로 찾는 문제가 됨.
1. n개의 점을 잡고, 각각 1부터 n까지의 번호를 부여한다.
2. 두 점의 번호 합이 자연수의 제곱이 된다면, 두 점을 잇는다. (10-6, 6-3, 15-21, etc.)
3. 점과 선이 다 만들어지면, 모든 점을 정확히 한 번씩만 방문하고, 시작점과 끝점이 같은 경로를 찾으면 됨.