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

[문제 출처]

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

1699번: 제곱수의 합

 

[문제 풀이]

인덱스 값으로 초기화를 한 크기가 n+1인 리스트를 선언하여 시작한다.

리스트의 값들은 해당하는 인덱스의 값을 제곱수의 합으로 나타내었을 때 항의 최소 개수이다.

 

모든 수들은 1의 제곱으로 표현할 수 있기에 초깃값은 자기 자신과 같은 값으로 초기화한다.

2중 for문을 통해 i보다 작은 j의 제곱들의 항의 개수들을 비교하여 그중에서 가장 작은 값 + 1을 리스트에 저장한다.

 

이 문제는 시간 초과 때문에 오래 걸린 문제이다.

2가지 때문에 시간초과가 발생했는데

첫 번째는

제곱을 나타내기 위해서 j*j 대신에 j**2를 사용한 것이고,

두 번째는

min함수를 사용한 것이다.

 

이 부분만 조심하면 어렵지 않게 풀 수 있는 문제이다.

n = int(input())

dp = [i for i in range(n+1)]

for i in range(2, 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])