[Python - Dynamic Programming] 1699 제곱수의 합

📌 문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=3²+1²+1²(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=2²+2²+1²+1²+1²(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

📌 입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

📌 출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

전체적인 양상이 다이나믹 프로그래밍을 통해서 이전 값을 참고해서 정답을 구하는 문제로 보인다.

 

예를 들어,

11 = 1 + 1 + 1 + ... + 1 + 1 + 1

     = 2 + 2 + 1 + 1+ 1

     = 3 + 1 + 1

이런 식으로 구할 수 있다. 제곱수를 미리 빼놓으면 나머지 수가 몇 개의 항을 필요로 하는지 구하는 것이다. 그래서 11은 d[3]에서 1을 더해주면 가장 최소인 항의 개수를 가질 수 있다. 혹은, d[제곱수] + d[값 - 제곱수]로 구해도 좋다.

👨‍🏫 문제 풀이

📄 전체 코드

n = int(input())
d = [0, 1, 2, 3]

for i in range(4, n + 1):
    d.append(i)
    k = 2
    while k ** 2 <= i:
        d[i] = min(d[i], d[i - k ** 2] + 1)
        k += 1

print(d[n])

📄 준비

n = int(input())
d = [0, 1, 2, 3]

0부터 3까지는 모두 1만을 항으로 가지기 때문에 미리 값을 넣어줬다.

📄 풀이

for i in range(4, n + 1):
    d.append(i)
    k = 2
    while k ** 2 <= i:
        d[i] = min(d[i], d[i - k ** 2] + 1)
        k += 1

print(d[n])

dp 테이블에 값을 넣어준 후에 연산을 해준다. 이때, i로 값을 넣는 이유는 가장 최후의 수단이 1로만 항을 구성하는 것이기 때문이다. 사실 수가 커질 수록 1로만 항을 구성하는 경우는 없으나 while 반복문에서 d[i] 를 사용하기 때문에 단순하게 i로 초기화 했다.

📌 총평

직접 파이썬을 실행했을 때 n이 100000일 때 시간이 너무 오래 걸려서 제출 안 했었는데, pypy로 제출하니까 통과됐다. pypy 짱