1699번 제곱수의 합1 [Java] BOJ 1699번 제곱수의 합 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 최대 항의 최대 개수는 1^2으로만 이루어진 경우이므로 memo[i] = i로 초기화하였습니다. i - (j ^ 2)인 수의 최대항의 개수 + 1중 최소인 값을 찾아 해결했습니다. 예를 들어 i = 5, j = 2라면 5 - (2 ^ 2) = 1이므로 memo[1]의 최대 항의 최소 개수는 1입니다. 때문에, 1 + (2 ^ 2)를 하면 원래 i인 5가 되므로 문제에서 요구한 제곱수의 합으로 표현되므로 memo[1] .. 2021. 4. 30. 이전 1 다음