Problem
Concept & Idea
처음에는 굳이 DP로 풀어야하나?라는 의문이 들어서 그냥 생각대로 풀었다.
수학문제 해결하듯이 풀어낸 코드는 다음과 같다.
#include <iostream>
#include <cmath>
using namespace std;
int n;
int main() {
cin>>n;
int cnt=0;
while(n!=0) {
int t=int(sqrt(n));
n-=t*t;
cnt+=1;
}
cout<<cnt<<endl;
}
역시나 틀렸고 그 반례는 다음과 같다.
12의 경우를 생각해보면, 9+1+1+1이 최소라고 생각했지만 4+4+4로 정답은 3이었다.
그래서 다시 DP로 돌아왔다.
이 문제에서 가장 중요한 것은 제곱수이다.
해당하는 map[i]에 i-jj에 해당하는 수의 +1보다 값이 큰지 작은지를 비교하면 해결할 수 있는 문제였다.
이 jj를 포문으로 풀면 금방 해답을 찾을 수 있었다.
Code
#include <iostream>
#include <vector>
using namespace std;
int n;
int map[100001];
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
map[i]=i;
for(int j=1; j*j<=i; j++) {
if(map[i]>map[i-j*j]+1) {
map[i]=map[i-j*j]+1;
}
}
}
cout<<map[n]<<endl;
}
Fealing
역시 분류가 다이나믹 프로그래밍으로 되어있는것은 다 그 이유가 있는 것이다..
손으로 하나하나 써가면서 진지하게 고민해보아야 한다.
Check out this code in Victoria’s Gist. Please Comment my code in this link.