[백준] 제곱수의 합 / 파이썬(python)

# 문제 링크

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

1699번: 제곱수의 합

# Soultion

처음에는 단순히 제곱근이 큰거부터 한개씩 제거했더니 문제가 발생하였다.12같은 경우는 9+1+1+1이므로 4개가 되는데, 실제로 최소값은 4+4+4이므로 모든 경우의 수를 확인해야하는 문제이다.

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

 

3. 각 숫자들의 최소 제곱근을 저장하기위한 리스트이다. 각 숫자들은 1의 제곱근으로 만들 수 있으므로 자기자신으로 초기화

5. n까지 한개씩 계산하기

7. 제곱근의 값이 현재 값보다 커지면 멈추기(이 문장이 없으면 시간초과발생)

9. 새로구한 제곱근의 개수가 원래저장되어있는 개수보다 작으면 값을 새로업데이트해준다. 

  이때, 1을 더해주는 이유는 dp[i-j*j]에서 j*j라는 숫자를 더해준것이므로 1더하여 계산해준다.