[백준] 1699. 제곱수의 합(Python, 파이썬)

백준 온라인의 문제 풀이입니다.

📖 [백준] 1699. 제곱수의 합

시간 제한	메모리 제한	난이도
2초	128 MB	난이도

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

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

✔️ 입력

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

✔️ 출력

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

✔️ 입력 출력 예시

입력	출력
7	4
1	1
4	1
11	3
13	2

🗒️ 내 풀이

dp[n]이 제곱수 항의 최소 개수라고 하면, 점화식은 dp[n] = min(d[n - k * k] + 1)이 된다.

즉, 낮은 값에서 제곱수 만큼씩 더하는게 가장 항이 적다는 뜻이다. ex) 19라면, dp[18(19-1)] + 1, dp[15(19-4)] + 1, dp[10(19-9)] + 1, dp[3(19-16)] + 1 중 가장 작은 값이 dp[19]가 된다.

근데, 처음에 아래의 코드와 같이 min()을 사용하니 시간초과가 발생했다.

그래서 구글링을 하다보니.. 같은 알고리즘인데도 다른 분들은 if 문으로 비교연산자를 사용하니 통과하는 것을 보고 바꿨더니 통과했다.

🗒️ 처음 풀이(틀림)

import sys
input = sys.stdin.readline
n = int(input())
dp = [x for x in range(n + 1)]

# d[n] = min(d[n - k^2] + 1)
for i in range(2, n + 1):
    k = 1
    while k * k <= i:
        dp[i] = min(dp[i], dp[i - k * k] + 1)  # 시간초과 발생
        k += 1
print(dp[n])

수정 코드

import sys
input = sys.stdin.readline
n = int(input())
dp = [x for x in range(n + 1)]

# d[n] = min(d[n - k^2] + 1)
for i in range(2, n + 1):
    k = 1
    while k * k <= i:
        if dp[i] > dp[i - k * k] + 1:  # 시간초과 해결
            dp[i] = dp[i - k * k] + 1
        k += 1
print(dp[n])

💡 TIL

min() 함수는 O(N)의 시간 복잡도를 가짐. 단순 비교 연산자보다 시간이 오래걸리는 것을 알았다!