백준 1699_제곱수의 합

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

# 시간초과
N = int(input())
M = int(N ** 0.5)
dp = [n for n in range(N+1)]

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

# 업데이트 대상인 값만 처리하자
N = int(input())
M = int(N ** 0.5)
dp = [n for n in range(N+1)]

for i in range(2, M + 1):
    for j in range(i*i, N + 1):
        dp[j] = min(dp[j],dp[j-i*i] + 1)
print(dp[N])

• 이 문제는 제곱수의 합이 N이 될 수 있는 제곱수의 최소 갯수를 구하는 문제다.
• 제곱수 중 가장 작은 값인 1로 먼저 dp테이블을 채우고 다른 제곱수 들이 더해졌을 때 해당값을 만드는 최소 갯수를 dp테이블에 업데이트 해야한다.
• 그렇기 때문에 dp테이블이 2차원으로 필요하다.

• 💯 dp테이블을 2차원으로 만드는 것도 생각하자!!
• 💯 더 나아가면 2차원으로 구상한 테이블을 1차원으로 만들도록 생각해보자