[백준] 1699 제곱수의 합 파이썬 python

문제링크

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

1699번: 제곱수의 합

 

코드

import sys
input = sys.stdin.readline
 
n = int(input())
d = list(range(100001))
 
for i in range(4,n+1):
    if int(i**(1/2))**2 == i:
        d[i] = 1
        pass
    tmp = d[i]
    for j in range(1,i//2+1):
        if tmp>d[j]+d[i-j]:
            tmp = d[j]+d[i-j]
    d[i] = tmp 
print(d[n])

 

POINT

- DP로 접근

- 풀이방법:

'd[i] = i를 그 합으로써 표현할 제곱수 항의 최소 개수' 로 정의한다. 

ex) d[4] = 1 (4=2^2), d[5] = 2 (5=2^2+1^2), d[6] = 3 (6=2^2+1^2+1^2),

d[10]=2 (10 = 3^2+1^2)

 

 

이후, DP를 적용하여 다음과 같은 과정을 거친다.

5를 만들기 위해선, 5 자체가 제곱수인가 vs 5 = 1+4 vs 5 = 2+3 중 비교하기!

 

5가 제곱수인가?(=1) vs d[1]+d[4]+ vs d[2]+d[3] 중 최소로 갱신

6이 제곱수?(=1) vs d[1]+d[5]+ vs d[2]+d[4]+ vs d[3]+d[3] 중 최소로 갱신 

 

 

* 완전제곱수 판별 방법

(i**(1/2))**2 == i 으로 하면 파이썬 내부 버림 때문에 11과 같은 수도 제곱수로 오판된다. 

따라서, int()를 활용하여  int(i**(1/2))**2 == i 다음과 같이 해결한다.