1699 - 제곱수의 합

1) 문제 링크 

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

2) 문제 설명

어떤 자연수를 제곱수로 나타낼 수 있다

ex ) 11 = 3^2 + 1^2 + 1^2    -> 3개로 가능

 

3) 문제 풀이 

처음에는 받은 수 n 의 sqrt를 구해서 해볼 생각이었다. (수학 + 구현 문제인줄..)

예를 들어서 11이면

int(math.sqrt(11)) = 3

11 - 3^2 = 2

int(math.sqrt(2)) = 1

2 - 1^2 = 1

int(math.sqrt(2)) = 1

2 - 1^2 = 1

이렇게 해서 3번이 나온다

 

결과는 실패...

 

코드는 간결했다. 그러나 틀렸다.

import math
n = int(input())

cnt = 0
while n > 0:
    num = int(math.sqrt(n))
    n -= num ** 2
    cnt += 1
print(cnt)

 

뭔가 문제가 있다. 

 

DP로 풀어봐야겠다 

1 = 1^2

2 = 1^2 + 1^2

3 = 1^2 + 1^2 + 1^2

4 = 2^2

5 = 2^2 + 1^2

6 = 2^2 + 1^2 + 1^2

7 = 2^2 + 1^2 + 1^2 + 1^2

8 = 2^2 + 2^2

9 = 3^2

10 = 3^2 + 1^2

 

즉 제곱수가 나눠져 떨어지는 구간..1, 4, 9, 16에서 제곱수 값이 갱신되고

4 와 9 사이에는 1이 반복되는걸 볼 수 있다

 

이걸 점화식화하면 

dp[i] = min(dp[i], dp[i - j**2] + 1)이다

+1을 하는 이유는 자기 자신을 포함해야기때문이다

sqrt를 사용해서 빈도수를 줄일 수 있다.

import math
n = int(input())

dp = [x for x in range(n+1)]

for i in range(1, n+1):
    for j in range(1, int(math.sqrt(i)+1)):
        dp[i] = min(dp[i], dp[i - (j**2)]+1)
print(dp[n])