(Python)백준 코딩테스트 연습 - 제곱수의 합(1699)

1. 문제

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

1699번: 제곱수의 합

2. 풀이

import sys
input = sys.stdin.readline
import math

# n : 제곱의 합들로 나타낼 자연수
n = int(input())

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

for i in range(1, n+1):
    for j in range(1, int(math.sqrt(i)) + 1):
        dp[i] = min(dp[i], dp[i - (j ** 2)] + 1)
print(dp[n])

3. FeedBack

 - 이번 문제는 다이나믹 프로그래밍을 사용하는 문제이다.

 다양한 DP 코딩들은 기본적으로 사전에 연산된 결과값을 저장해두고 차후 같은 연산을 해야할 상황이 오는 경우 연산하지 않고, 저장된 값을 사용하는 방식을 활용하게 되는데, 기본적인 개념은 같지만 상황에 따라 어떤 결과값을 사용해야할지를 결정하여 코딩하는 것이 개발자의 실력이 드러나는 부분인것 같다.

 개발자로서 이러한 능력을 쌓아가기 위해 계속 노력해야겠다.