[백준 알고리즘] 1699번 제곱합. 파이썬(python)

오답)

틀린 이유: n보다 작은 제곱값 중 제일 큰 수를 빼는 것을 반복하면 최소가 나올 줄 알았다.

예제로 나온 값들도 결과가 맞았었다.

그런데 52와 같은 반례를 보니 틀린 것을 알 수 있었다.

52=49+1+1+1 로 큰수를 빼면 정답이 4이지만,

52=36+16으로 계산하면 2번만에 구할 수 있다.

따라서 dp를 사용해 각 값의 최소연산 수를 구해야 한다.

import sys
input=sys.stdin.readline

n=int(input())
sq=[i*i for i in range(1,318)]
cnt=0
while n!=0:
    for i in range(len(sq)):
        if sq[i]>n: # 작은값 중에 제일 큰 값
            n=n-sq[i-1]
            cnt+=1
            break
print(cnt)

 

정답)

import sys
input=sys.stdin.readline

n=int(input())
sq=[i*i for i in range(1,318)]
dp=[0]*(n+1)

for i in range(1,n+1):
    s=[]
    for j in sq:
        if j>i:
            break
        s.append(dp[i-j])
    dp[i]=min(s)+1

print(dp[n])