백준: 1699 제곱수의 합

문제

1699번: 제곱수의 합

 

문제 풀이

 자연수 N이 주어지면 해당 수를 제곱수들의 합으로 나타낼 때 항의 최소 개수를 구하는 문제이다. N에 따라서 항의 최소 개수를 비교하면 문제를 쉽게 풀 수 있다.

 

N	항	항의 최소 개수
0	없음	0
1	1 ^ 2	1
2	1 ^ 2 + 1 ^ 2	2
3	1 ^ 2 + 1 ^ 2 + 1 ^ 2	3
4	2 ^ 2	1
5	2 ^ 2 + 1 ^ 2	2
6	2 ^ 2 + 1 ^ 2 + 1 ^ 2	3
7	2 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2	4
8	2 ^ 2 + 2 ^ 2	2
9	3 ^ 2	1

 위와 같이 N이 증가함에 따라 규칙성을 같는 것을 알 수 있다.  이로써 점화식은 f(n) = min(f(n), f(가능한 최대제곱수) + 1)가 된다는 것을 알 수 있다. 표와 점화식이 이해가 잘되지 않더라도 코드를 보고 이해할 수 있다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())

    answer = [0] * (n + 1)

    for i in range(1, n + 1):
        answer[i] = i
        for j in range(1, i):
            if j * j > i:
                break
            if answer[i] > answer[i - j * j] + 1:
                answer[i] = answer[i - j * j] + 1
    print(answer[n])

 9인 경우 계산되는 과정을 보면, 다음과 같다.

• 반복문을 시작하면, 9의 인덱스로 초기화 한다. (이는 모두 1^2으로 나타냄을 의미한다)
• j를 증가 시키면서 9의 경우 2^2, 3^3을 경우의 수로 둘 수 있다.
  • [9 - 2^2] + 1은 N:5 + 1을 의미한다 즉 2^2 + 2^2 + 2^1을 의미한다.
  • [9 - 3^2] + 1은 N:0 + 1을 의미한다. 즉 3^2를 의미한다.
  • 9, 3, 1 중 최소 값은 1이므로 9를 나타낼 수 있는 제곱수 항의 최소 값을 찾을 수있다.

 이와 같이 i(N)가 증가 할 수록 항에 적용할 수 있는 제곱수는 증가하므로, 가장 큰 제곱수가 만족하고, 이전 값을 메모이제이션하였기에 답을 찾을 수 있다.