[BOJ] 제곱수의 합(1699) - PYTHON

1~100,000 사이의 자연수 N을 제곱수들의 합으로 나타낼 때, 가능한 경우의 수에서 항의 최소 개수를 구하는 문제다. 

시간 복잡도: O(N)

---

풀이 과정

어떤 규칙으로 나타낼 수 있을지 생각이 안 나서 1부터 숫자들을 제곱수로 나타내 봤다.

1부터 12까지 제곱수의 합

제곱수 하나로 만들어질 수 있는 1, 4, 9에서 수가 커질수록 1의 제곱이 1씩 붙는 경우가 많다. 하지만 8, 12처럼 뒤에 1의 제곱이 아니라 다른 수가 붙는 경우도 있어 규칙이 존재하지는 않는다.

그런데 여기서 N에 대해 제곱수의 합으로 나타내려고 할 때, 그 항의 개수는 N에서 어떤 제곱수를 뺀 값에서의 항 개수 + 1과 같다. 12의 경우를 다시 살펴보자.

N = 12 일때 나올 수 있는 경우의 수

N = 12일 때 정답 값은 N = 8일 때 정답 값 + 1이다.
하지만 나올 수 있는 경우는 N = 11일 때 정답 값 + 1, N = 3일 때 정답 값 + 1이다. 각각 2,1,3의 제곱수를 더해서 구할 수 있다.
즉 동적 계획법을 통해 1 ~ N까지  값을 구해서 배열에 저장하며, 값은 dp[N - 제곱수] + 1이다.

---

코드

from math import sqrt
 
N = int(input())
dp = [0] * (N + 1)
squareNum = []
for i in range(1, int(sqrt(N) + 1)):
    squareNum.append(i * i)
for i in range(1, N + 1):
    dp[i] = i
    for snum in squareNum:
        if i < snum:
            break
        dp[i] = min(dp[i], dp[i - snum] + 1)
print(dp[N])

 

주석 추가

from math import sqrt
 
N = int(input())
dp = [0] * (N + 1)  # 1 ~ N까지 값을 저장할 배열
squareNum = []  # N보다 작은 제곱수를 저장할 배열 (ex. N = 12일 경우 [1, 4, 9])
for i in range(1, int(sqrt(N) + 1)):  # 1부터 sqrt(N)까지 반복하며
    squareNum.append(i * i)  # 제곱수를 배열에 추가
for i in range(1, N + 1):  # 1부터 N까지 dp배열 값 채우기
    dp[i] = i  # 초기 값은 1^2의 합으로만 구성한 값
    for snum in squareNum:  # 제곱수를 하나씩 꺼내서
        if i < snum:  # 제곱수가 i보다 크다면 (ex. N = 12, i = 8, 제곱수 = 9 일때)
            break  # 반복문 탈출
        dp[i] = min(dp[i], dp[i - snum] + 1)  # dp값 업데이트 dp[i - 제곱수] + 1과 원래 값 중 더 작은 값
print(dp[N])  # 배열의 N번째 값(정답) 출력

---

채점 결과

첫 시도에서는 문제에서 나올 수 있는 경우의 수를 제대로 나누지 못해서 틀렸다.

이후 시간 복잡도가 O(N^2)인 방법밖에 생각이 안 나서 게시판을 통해서 힌트를 얻고 O(N)인 방법으로 풀었다.

PYTHON3로 채점하면 시간 초과가 나는 경우가 있다고 해서 PYPY3로 채점했다.