2022-08-21 @이영훈
접근방법
처음에는 그리디 문제로 알고 접근했습니다. 제곱해서 가장 큰 수를 빼고 그 다음 큰 수를 제곱해서 빼는 방식으로 생각했습니다.
하지만 12의 경우 위의 방법으로 접근하면, 12 = 3^2 + 1^2 + 1^2 + 1^2로 4가 됩니다. 하지만 가장 적은 경우는 12 = 2^2 + 2^2 + 2^2로 3입니다.
다이나믹 프로그래밍 문제입니다. 다이나믹 프로그래밍 문제는 규칙을 찾을 때까지 적어보는 게 좋습니다.
위의 경우로 보면, 1, 4, 9, 16은 자연수를 제곱한 수 입니다.
그리고 7을 예로 들어보면, dp[7] = dp[4] + dp[3] 입니다
12를 보면, dp[12] = min(dp[4] + dp[4] + dp[4], dp[9] + dp[3]) = dp[4] + dp[8] 입니다
15를 보면, dp[15] = min(dp[9] + dp[4] + dp[2], dp[4] + dp[4] + dp[4] + dp[3]) = dp[9] + dp[4] + dp[2] 입니다
이와 같이 제곱수를 기준으로 모든 경우를 다 계산해서 최소의 값이 되는 것을 저장합니다.
파이썬 코드
number = int(input())
dp = [i for i in range(number + 1)]
for i in range(2, number + 1):
for j in range(1, i + 1):
square = j * j
if square > i:
break
if dp[i] > dp[i - square] + 1:
dp[i] = dp[i - square] + 1
print(dp[number])
Python
복사
시행착오
# 🐰 faster
if dp[i] > dp[i - square] + 1:
dp[i] = dp[i - square] + 1
# 🦉 slower -> timeout
dp[i] = min(dp[i], dp[i - square] + 1);
Python
복사
생각해보면 아래 쪽이 연산량이 더 많다. 비교 연산(min)은 연산대로 하고, 메모리에 숫자 할당도 하기 때문이다.