[알고리즘/자바] 백준 1699번 - 제곱수의 합

1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀고나면 별거 아닌것 같은데 정답까지 생각이 도달하는데 시간이 꽤 걸렸다. ( 입력이 10 일때 ) dp[10]을 구하기 위해서 이전에 구한 dp[1] ~ dp[9]를 활용할 수 있는 방향으로 머리를 굴렸다. dp[i] = i를 구하기 위한 최소 항 갯수로 dp를 셋팅하고 아래 처럼 모두 적었다. 위에 작성한 부분을 잘보면 dp[10]을 구하기 위해선 아래와 같은 방법을 사용할 수 있다. 이를 코드로 구현하면 아래와 같다...

2021.01.18