[백준 1699] 제곱수의 합 (Python)

김용범·2024년 12월 10일

문제 💁🏻‍♂️

해결 과정

나는 DP 유형문제를 정복하기 위해서 관련 문제집을 통해서 문제를 풀고 있었기 때문에 해당 문제가 DP 유형이라는 것을 미리 알았다. 문제도 뭔가 쉬워보여서 바로 풀이를 시작했지만, 역시나 바로 틀렸다.풀이까지의 사고 과정은 다음과 같다.

사고 과정 (1) ❗️

문제로 주어지는 N의 값은 1 <= N <= 100_000 이다. 즉, O(N^2)은 시간초과가 날 것이다. 따라서 최대한 O(N log N) 이하의 알고리즘으로 문제를 풀어야 한다. 그래서 나는 이 문제를 다음과 같은 순서로 접근했다.

우선, dp 테이블을 선언하고, 1부터 100_000 까지의 제곱수의 dp값을 1로 설정했다. 이를 위해서 math 라이브러리의 isqrt 함수를 사용했다.
100_000의 제곱근은 316 이다. 즉, 1부터 316까지만 돌면 된다.
1부터 100_000까지 돌면서 제곱수가 나오게 되면(if dp[i] == 1) 해당 제곱수를 기준값(std = i)으로 설정한다.
기준값이 아닌 경우에는 dp[i] = dp[i - std] + 1 라는 점화식으로 dp 테이블을 완성하고, dp[n] 값을 출력한다.

이 풀이는 치명적인 단점이 있다. 반드시 특정 숫자와 가장 가까우면서 가장 큰 제곱수로만 dp 값을 채운다는 것이 틀린 이유였다.

예를 들어, 41 이라는 숫자가 있다. 내가 설정한 점화식은 41 = 36 + 4 + 1 을 정답으로 내보낸다. 그러나, 사실은 41 = 25 + 16 가 정답이다.

사고 과정 (2) ‼️

그럼 이 문제를 어떻게 풀이할까... 생각하다가 100_000보다 작으면서 가장 큰 제곱수가 316의 제곱이라는 것이 눈에 보였다. 즉, 완전 탐색을 돌려도 O(316N) = O(N) 이기 때문에 통과할 것이라고 판단을 내리고 완전 탐색을 하기로 마음을 먹었다. 완전 탐색의 과정은 다음과 같다.

1) 사고 과정 (1)의 풀이 방향과 비슷하다.
2) 1부터 100_000까지 돌면서 특정 숫자보다 작은 모든 제곱수들에 대해서 dp[i] = dp[i -j * j] + 1 점화식을 적용하기로 했다.
3) 예를 들어, 현재 숫자가 41일 이라고 하자. 설정한 점화식으로 dp값이 갱신되는 과정은 다음과 같다.

      dp[41] = dp[41 - 2 * 2] + 1 = dp[37] + 1 = 3
      dp[41] = dp[41 - 3 * 3] + 1 = dp[32] + 1 = 3
      dp[41] = dp[41 - 4 * 4] + 1 = dp[25] + 1 = 2
      ...
      dp[41] = dp[41 - 6 * 6] + 1 = dp[5] + 1 = 3
      # 점화식 
      dp[i] = min(dp[i], dp[i - j * j] + 1)

이렇게 코드를 고치니, 문제를 해결할 수 있었다!

코드

오답 코드

from sys import stdin
from math import isqrt

input = stdin.readline

n = int(input().rstrip())

LEN = 100_000
# dp 초기화
dp = [0 for _ in range(LEN + 1)]
for i in range(1, isqrt(LEN) + 1):
    dp[i ** 2] = 1

std = None
for i in range(1, LEN + 1):
    if dp[i] == 1:
        std = i
        continue

    dp[i] = dp[i - std] + 1

print(dp[n])

정답 코드

from sys import stdin
from math import isqrt

input = stdin.readline

n = int(input().rstrip())

LEN = 100_000
# dp 초기화
dp = [float('inf') for _ in range(LEN + 1)]
for i in range(1, isqrt(LEN) + 1):
    dp[i ** 2] = 1

# 문제 풀이
for i in range(1, LEN + 1):
    for j in range(1, isqrt(i) + 1):
        dp[i] = min(dp[i], dp[i - j * j] + 1)

print(dp[n])