[문제 보러 가기]
이 문제는 2번째로 많이 풀린 문제(103회 AC) 이나, 정답율은 10.47% 로 저조한 편입니다. 아마도 brute force 방법을 통한 시간 제한 초과, 잘못된 greedy approach를 이용한 WA유발이 저조한 정답율의 원인이 되지 않았을까 하는 생각이 듭니다.
실제로 greedy approach를 시도하여 AC를 맞은 팀도 있었으나, 이번 에디토리얼에서는 dynamic programming을 이용한 해법을 설명하고자 합니다.
처음으로 알아 둬야 할 것은 x^2 <= 100,000 일 경우 최대의 x는 몇인가 라는 것인데, 범위 안에 들어가는 가장 작은 제곱수는 361^2 입니다.
다음으로 table[i][n]을 완성하는데, 여기서 table[i][n]은 숫자 n을 1^2 이상 i^2 이하 완전 제곱수 집합의 합으로 표현 할 경우의 최소의 사용 숫자 횟수를 뜻합니다.
0 의 경우 어떤 완전 제곱수 없이 완성 할 수 있는 숫자 이므로 table[0][0] = 0, 이며 이것이 점화 관계의 시작이 됩니다.
위의 사실을 통해 세워지는 점화식은 다음과 같습니다.
[spoiler="더 보기..."]table[i][n] = min(table[i-1][n],table[i][n-i^2]+1) ( ∵ 1<=i<=361, n-i^2>=0)
[/spoiler]
위의 점화식은 그대로 코드로 옮길 수 있으나, 이 경우 362 * 100,000 크기의 배열을 요구하므로 공간 복잡도 측면에서 비효율적인 프로그램을 작성하게 됩니다. 하지만 위의 점화식을 보았을때, i^2을 쓰는 단계에선 자신에게 필요한 것은 바로 위의 (i-1)^2의 행 만을 필요로 하며, (i-1)^2의 행을 유지하고 그 다음 상태에 대해 갱신을 하더라도 문제가 없기 때문에 다음과 같이 구현이 가능합니다.
[spoiler="더 보기..."]vector D(100001,(1<<30)); // 0~100,000까지의 1차원 배열을 잡고, 배열의 원소의 초기값은 2^30 으로
D[0] = 0;
for(int i=1;i<=361;++i) {
int sqr = i * i;
for(int j=sqr;j<=100000;++j) D[j] <?= D[j-s] + 1; // a <?= b 는 a = a < b ? a : b 와 같다. g++ 에서 허용되는 extension
}[/spoiler]

• 정현환, algospot.com 운영자
  [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]