[BOJ] 1699 / 제곱수의 합 / Python 파이썬

[BOJ] 1699 / 제곱수의 합 / Python 파이썬

[BOJ] 1699 / 제곱수의 합 / Python 파이썬

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

1699번: 제곱수의 합

 

풀이

주어진 숫자와 제곱수와의 차이를 생각하는것이 문제의 해결 방법이었다.

 

N = 1 -> 1                -> 1
N = 2 -> 1 + 1            -> 2
N = 3 -> 1 + 1 + 1        -> 3
N = 4 -> 2                -> 1
N = 5 -> 2 + 1            -> 2
N = 6 -> 2 + 1 + 1        -> 3
N = 7 -> 2 + 1 + 1 + 1    -> 4
N = 8 -> 2 + 2            -> 2
N = 9 -> 3                -> 1
N = 10 -> 3 + 1           -> 2
N = 11 -> 3 + 1 + 1       -> 3
N = 12 -> 2 + 2 + 2       -> 3
N = 13 -> 3 + 2           -> 2
N = 14 -> 3 + 2 + 1       -> 3
N = 15 -> 3 + 2 + 1 + 1   -> 4
N = 16 -> 4               -> 1

 

주어진 숫자가 제곱수라면 제곱수의 합은 항상 1 이 된다.

그러므로, 주어진 숫자와 제 수와의 차이가 제곱수의 합의 결과가 된다.

 

물론 8 과 12 등의 반례도 존재한다.

 

이러한 반례들을 고려 하였을때, dp 를 이용하여 최소 값을 구해 나가야한다.

 

N = int(input())

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

for i in range(1, N+1):
    tmp = []
    for j in range(1, i):
        if j*j > i:
            break
        tmp.append(dp[i - j*j])
    if tmp:
        dp[i] = min(tmp) + 1
        
print(dp[N])

 

경우의 수를 나열 하였을 때, 제곱으로 만들어지는 수와 제곱수와의 관계는 생각하였지만,

답을 계산하는 것 까지 도달하지 못하였다.

 

다른 분들의 풀이를 참고 하였지만, 와 닿지 않는 상태이기도 하다.

 

 

---

참고 블로그

https://jyeonnyang2.tistory.com/50

[Python] 백준 1699번: 제곱수의 합 풀이

https://pacific-ocean.tistory.com/205

[백준] 1699번(python 파이썬)