백준 1699

백준 1699 제곱수의 합(Java)

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 해석 및 팁 이 문제는 백준 17626 Four Squares 문제와 같은 문제입니다. 이문제도 다이나믹프로그래밍으로 풀어야 하는데 점화식은 dp [N] = min(dp[N], dp[N - 제곱수] + dp[제곱수]) 일댸 dp[제곱수] = 1 이므로 dp[N - 제곱수]만 구해주면 됩니다. Java 코드 import java.util.Scanner; pub..