백준 1699 제곱수의 합 Java
2019. 4. 15.
정답률 41퍼센트의 dp 문제이다. 왜 41퍼센트인지 모를 정도로 점화식 세우기가 어려웠다.. 마지막 자리에 올 수 있는 수는 1^2, 2^2, 3^2 등등 어떤수의 제곱인 i^2이다. 그리고 i^2 앞에는 n-i^2이다. 뒤에 i^2이 왔으니 n에 i^2을 빼야 하는 것이다. 그리고 dp배열에는 최종적으로 항의 개수가 들어가야 한다. 최종적으로 식은 n-i^2+i^2이므로 항 n-i^2에 +1을 해줘야 한다. 무슨소리인지 이해하기 힘들지만 이해하려고 하면 이해가 된다. 그렇게 점화식을 세우면 dp[n] = Math.min(dp[n-i^2]+1) //가능한 i범위 중에서 최소값 저렇게 세워진다. 1 2 3 4 5 6 7 8 9 10 11 12 13 public static void main(String[..