[백준] 제곱수의 합

출처:: www.acmicpc.net/problem/1699

분류:: dp

 

1. 문제 이해 및 해결과정

- dp : i를 표현할 수 있는 제곱수의 합의 최소 개수 1 1 2 2 3 3 4 1 5 2(4+1) 6 3(4+1+1) 7 4(4+1+1+1) 8 2(4+4) 9 1(9) 10 2(9+1) 11 3(9+1+1) 12 3(4+4+4)

 

2. 풀이방법

  1. [python] dp

#제곱수의 합
#https://www.acmicpc.net/problem/1699
import sys
import math
sys.stdin = open("input.txt","r")
n=int(input())
dp=[0]*(n+1) 

for i in range(1,n+1):
    dp[i]=i
    for j in range(1,i):
        if (j*j)>i: #제곱수가 더 크면 stop
            # print(j)
            break
        #print(dp[i-j*j]+1,dp[i])
        dp[i]=min(dp[i-j*j]+1,dp[i])

print(dp[n])

 

 

3. 오답원인

  1. 10까지 고려했을 떄, i까지 중 가장 큰 제곱수 + 알파 라고 생각했는데, 12의 경우 9+1+1+1 가 아니라 4+4+4 가 될 수 있다. 모든 제곱수의 경우를 고려해야한다. 

- 밑에는 아예 틀린 풀이이다. 

#제곱수의 합
#https://www.acmicpc.net/problem/1699
import sys
import math
n=int(input())
dp=[100001]*(n+1)

for i in range(1,n+1):
    if math.sqrt(i)*math.sqrt(i)==i: #제곱수라면
        twin=i #i까지 중 가장 큰 제곱수 저장
        dp[i]=1
    else:
        # print(i,twin)
        if i>twin:
            dp[i]=min(dp[i-twin]+1,dp[i])
        else:
            dp[i]=dp[i-1]+1
print(dp[n])

 

4. 알게된 점