백준 1699 제곱수의합 파이썬

백준 1699 제곱수의합 풀이

접근방식

1. 1부터 9까지 직접 제곱수의 합을 표현해본다.
2. 발견한 패턴 : 해당 숫자에서 제곱수를 빼고 남은 수의 개수에 1을 더한 값과 비교하여 더 작은 것을 고른다.

3. 예 : n = 11일 경우, dp[11-1]	dp[11-4]	dp[11-9] 를 했을 경우,
   => dp[10]	dp[7]	dp[2] 중, dp[2]가 가장 적은 개수인 2이므로 여기에 1을 더한 값이 dp[11]이 된다.

4. min 함수를 사용할 경우 런타임에러가 나기 때문에 if문으로 대소비교를 해준다.
5. 더 빠른 계산을 위해 pypy3로 제출한다.

# 입력받기
import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

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


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

print(dp[n])

해당 문제는 실버3레벨에 해당하지만, 단순히 이전의 dp리스트에 더하면서 점화식을

구하는 문제들과는 조금 달라 체감 난이도가 더 있었다고 생각합니다.

따라서 다이나믹 프로그래밍 알고리즘에 대한 감각을 익히기에 매우 좋은 문제라고 생각합니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다. Just do it & Keep steady