[알고리즘][백준] 1699번 제곱수의 합 - 파이썬(python) 풀이

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

1699번: 제곱수의 합

---

나의 아이디어노트

 

import sys

import math

n = int(sys.stdin.readline())

d = [100000] * (n+1)

d[1] = 1

d[2] = 2

d[3] = 3

if n < 4:

    print(d[n])

else:

    for i in range(4, n+1):

        if i == (math.sqrt(i))**2:

            d[i] = 1

        else:

            for j in range(1, i//2+1):

                print(i, i-j, j, d[i-j] + d[j])

                d[i] = min(d[i-j] + d[j], d[i])

    print(d[n])

n=11에서 3이 나와야하는데 1로 나오는 오류 발생....

print(math.sqrt(11)**2)

위의 출력 결과가 11.0이 나왔다

 

조건을 아래와 같이 변경하니 제대로 출력!

 if str(math.sqrt(i)).endswith("0"):

 

그런데

n=1을 넣으니 인덱스가 범위에서 초과... 

 

n=1일때 d는 [100000, 100000]라서 d[2], d[3]에 값을 넣어주니 오류가 발생한 것

 

아래와 같이 수정하고 넣으니

import sys

import math

n = int(sys.stdin.readline())

d = [100000] * (n+3)

d[1] = 1

d[2] = 2

d[3] = 3

if n < 4:

    print(d[n])

else:

    for i in range(4, n+1):

        if str(math.sqrt(i)).endswith("0"):

            d[i] = 1

        else:

            for j in range(1, i//2+1):

                d[i] = min(d[i-j] + d[j], d[i])

    print(d[n])

출력초과 엔딩....

 

마지막 반복문에서 발생했을듯..

 

결국 다른분의 코드를 참고했다

import sys

n = int(sys.stdin.readline())

# [0 1 2 3 4 5 ...]
d = [x for x in range (n+1)]

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

d[2] > d[1] + 1 (X)
d[3] > d[2] + 1 (X)
d[4] > d[3] + 1 (X)
d[4] > d[0] + 1 (O)     d[4] = d[0] + 1 = 1
d[5] > d[4] + 1 (O)     d[5] = d[4] + 1 = 2
d[5] > d[1] + 1 (X)
d[6] > d[5] + 1 (O)     d[6] = d[5] + 1 = 3
d[6] > d[2] + 1 (O)     d[6] = d[2] + 1 = 3
d[7] > d[6] + 1 (O)     d[7] = d[6] + 1 = 4
d[7] > d[3] + 1 (X)
d[8] > d[7] + 1 (O)     d[8] = d[7] + 1 = 5
d[8] > d[4] + 1 (O)     d[8] = d[4] + 1 = 2

n=8일때 어떤식으로 동작하는지 적어보았다

 

아이디어는 맞았는데 아쉬운 문제