https://www.acmicpc.net/problem/1699

🥚문제

🥚입력/출력

🍳코드

import sys
import math
input = sys.stdin.readline

n = int(input().strip())

dp = [0]*(n+1)

# bottom-up 방식
def bottom_up(n):
    # 제곱수는 1로 초기화
    x = 1
    while x*x <= n:
        dp[x*x] = 1
        x += 1

    # n의 값이 0이 아니면(제곱수) 리턴
    if dp[n] != 0:
        return dp[n]

    for i in range(1, n+1):
        if dp[i] != 0:
            continue

        mini = i
        # j*j <= i인 것 중
        # dp[j*j] + dp[i-j*j]의 값이 최소인 것을
        # dp[i]의 값으로 갱신
        for j in range(1, int(math.sqrt(i)) + 1):
            if 1 + dp[i-j*j] < mini:
                mini = 1 + dp[i-j*j]  # 1 = dp[j*j]
        dp[i] = mini

    return dp[n]

print(bottom_up(n))

🧂아이디어

다이나믹 프로그래밍

• top-down으로 풀면 n이 커졌을 때 recursion error를 뱉어내서 bottom-up으로 풀이!

• dp[x] : 자연수 x를 제곱수의 합으로 표현할 때 그 항의 최소 개수를 저장

• x가 이미 제곱수일 때 (x = y*y (1 <= y < x) )
  • x를 제곱수의 합으로 표현했을 때 x = y^2이므로 항이 1개
  • 따라서 이미 제곱수인 x들(1, 4, 9, ...)에 대해 dp[x] = 1로 초기화 해준다

• x가 제곱수가 아닐 때 (2, 3, 5, 6, 7, 8, 10, 11, ...)
  • 우리의 목표는 항의 개수를 최소로 만드는 것이기 때문에 dp에 저장된 값이 "1"인 제곱수들을 활용하여 식을 만들어낼 것이다.
  • y*y <= x 인 모든 제곱수, y*y에 대하여
  • 1 + dp[x-y*y] (= dp[y*y] + dp[x - y*y] )를 한 값 중 최소값을 dp[x]에 저장한다.