[백준] 1699번 : 제곱수의 합

1699번: 제곱수의 합

1699번: 제곱수의 합

🤔 문제분석

전형적인 다이나믹 프로그래밍 문제이지만 저는 처음에 문제를 풀때 너비우선탐색으로 문제를 해결하였습니다. 다이나믹 프로그래밍 풀이법과 너비우선탐색 풀이법 둘다 문제 풀이를 해보겠습니다.

다이나믹 프로그래밍

i 번째 제곱 수를 구할때 이전에 구했던 제곱수를 참조하여 값을 구합니다. dp[i] = min(dp[i], dp[i-제곱수] + 1) 로 나타낼 수 있습니다. 아래를 예를 확인하면 이해가 빠르게 됩니다.

dp[0] = 0

dp[1] = dp[0] + 1 ( 제곱수 그 자체임으로 dp[0] + 1로 나타낸다 )

dp[2] = dp[1] + 1

dp[3] = dp[2] + 1

dp[4] = dp[0] + 1

dp[5] = dp[4] + 1 ( 1의 제곱을 더함 )

dp[6] = dp[5] + 1 ( 1의 제곱을 더함 )

dp[7] = dp[6] + 1 ( 1의 제곱을 더함 )

dp[8] = min(dp[4] + 1, dp[7] + 1) ( 1의 제곱을 더해서 온 값과 2의 제곱을 더해서 온 값중 작은값으로 갱신 )

너비우선탐색

제곱수의 큐를 만듭니다. 그리고 그 제곱수에 더할 제곱수의 리스트를 가지고 있습니다.

제곱수의 큐를 너비우선탐색하고, 제곱수의 리스트를 더해가면서 cost를 계산하여 현재값과 리스트에있는 제곱수를 더한값이 목표하고자하는 값에 도달한다면 cost값을 리턴합니다.

num값을 만나게 되는경우 이미 cost값은 최소값을 보장하기때문에, 덱큐 자료구조로 문제를 해결 할 수 있습니다.

💻 코드

다이나믹 프로그래밍

import sys
input = sys.stdin.readline

N = int(input())

dp = [i for i in range(N+1)]

for i in range(2, N+1):
    for j in range(1, i+1):
        squre = j*j
        if squre > i:
            break
        
        dp[i] = min(dp[i], dp[i-squre]+1)

print(dp[N])

너비우선탐색

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

queue = deque()
squre_number = []
vistied = [False for _ in range(N+1)]
vistied[1] = True
queue.append((1, 1))
squre_number.append(1)

i = 1
cnt = 1
while N >= i:
    cnt += 1
    i = cnt**2
    if N >= i:
        queue.append((i, 1))
        squre_number.append(i)
        vistied[i] = True

while queue:
    num, cost = queue.popleft()
    if num == N:
        print(cost)
        break
    
    for n in squre_number:
        if N >= n + num and not vistied[n+num]:
            vistied[n+num] = True
            queue.append((n+num, cost + 1))

🎯 피드백 및 개선사항

처음에 문제를 풀때에 다이나믹 프로그래밍 접근법으로 문제를 해결하고자 하였습니다. 처음에 접근법은 현재 num보다 작은 제곱수의 값을 찾아가면서 누적하는 식으로 문제를 해결하였고, 최소값을 찾을 수 없다는 것을 깨닫게 되었습니다.

import sys
import math
input = sys.stdin.readline

N = int(input())
dp = [0 for _ in range(N+1)]

i = 1
cnt = 1
while N >= i:
    dp[i] = 1
    cnt += 1
    i = cnt**2
    
def find(num):
    return int(math.sqrt(num)) ** 2
    
for i in range(2, N+1):
    start = i
    while start >= 1:
        num = find(start)
        if num == i:
            break
        
        dp[i] += dp[num]
        start -= num
        
print(dp[N])