(JAVA) 백준 1699번 : 제곱수의 합

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

안녕하세요.

 

DP(동적 프로그래밍) 문제 중 하나로,

 

처음에 깊게 생각하지 않아서 한 번 틀리고, 방향을 바꿔 맞출 수 있었다.

(사실 두 번 틀렸다.)

 

 

이 문제의 핵심은 이거다.

 

구하려고 하는 수 N의 제곱수의 합은 1 ~ N 까지의 수 중 제곱수인 수 + (n - 제곱수) 의 최소 제곱수 갯수 중 최소인 값 이다.

 

 

예를 들어보자.

 

13 = 2^2 + 2^2 + 2^2 + 1^1 이 될 수도 있지만,

최소인 경우는 역시 3^3 + 2^2 이다.

 

즉, 1 ~ 13중에서 제곱수인 것은 1, 4, 9 가 되고 이들의 최소 제곱수는 1이다.

 

그럼 13의 제곱수의 합이 최소가 되는 경우는 무엇이냐?

 

(13 - 1) 의 최소 제곱수의 합, (13 - 4)의 최소 제곱수의 합, (13 - 9)의 최소 제곱수의 합

 

중 가장 작은 값과 +1(1, 4, 9 등 제곱수의 개수는 1개 이니까) 이 된다.

 

 

이해했는가?

 

가장 개수가 적으려면 제곱수(1개) 를 포함해야 한다. 왜? 1개니까!! 1을 더하는 값이 최소가 되지 않겠는가?

 

 

이를 알면 별도의 매커니즘은 스스로 생각해서 작성할 수 있다.

 

필자는 헷갈려서 해설을 조금 참고했지만...

 

 

하단 소스코드를 참고하면 된다.

 

 

감사합니다!

 

소스코드

---