https://www.acmicpc.net/problem/1699
실패이유 : 구현실패
n = int(input())
d = [i for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, int(i ** (1 / 2)) + 1):
if d[i] > d[i - j * j] + 1:
d[i] = d[i - j * j] + 1
print(d[n])
- 일반적인 다이나믹 프로그래밍의 문제풀이
- 구하려는 정답인 마지막 단계와, 바로 전 단계로 나눈다.
- 둘의 관계를 통해 점화식을 찾는다.
출처: 코드플러스 - 알고리즘 기초 1/2 강의
https://code.plus/course/41
