Problem
Concept & Idea
처음에는 굳이 DP로 풀어야하나?라는 의문이 들어서 그냥 생각대로 풀었다.
수학문제 해결하듯이 풀어낸 코드는 다음과 같다.
역시나 틀렸고 그 반례는 다음과 같다.
12의 경우를 생각해보면, 9+1+1+1이 최소라고 생각했지만 4+4+4로 정답은 3이었다.
그래서 다시 DP로 돌아왔다.
이 문제에서 가장 중요한 것은 제곱수이다.
해당하는 map[i]에 i-jj에 해당하는 수의 +1보다 값이 큰지 작은지를 비교하면 해결할 수 있는 문제였다.
이 jj를 포문으로 풀면 금방 해답을 찾을 수 있었다.
Code
Fealing
역시 분류가 다이나믹 프로그래밍으로 되어있는것은 다 그 이유가 있는 것이다..
손으로 하나하나 써가면서 진지하게 고민해보아야 한다.
Check out this code in Victoria’s Gist. Please Comment my code in this link.