정석적인 느낌에 제곱이라는 변수를 준 다이나믹 프로그래밍 문제로 보인다
먼저 든 생각은 어차피 아무리 커져도 N의 제곱근의 내림을 초과할 수는 없기 때문에 이를 먼저 구하려 했다
그렇다면
int a = int(sqrt(N));으로 정리해서 대입하면 되지 않을까? 생각을 했다
이걸 어디에 넣을까 싶다가 깔끔하게 for 안에서 정리하고, 0 ~ N까지 빼볼 때 접근하기 쉬우려면 for 앞에 넣는게 쉬울 것 같았다
아무튼 이렇게 해서 완성한 코드는
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int N;
cin >> N;
const int INF = 1e9;
vector<int> dp(N + 1, INF);
dp[0] = 0;
for(int i = 1; i <= N; i++) {
int a = (int)sqrt(i);
for (int j = 1; j <= a; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
cout << dp[N] << '\n';
}한줄 한줄 설명해보자면
결론적으론 더한 갯수의 최솟값을 구하려면 min을 잡아야 하기 때문에
0 ~ N+1, 즉 실제 벡터에 명시된 수가 N이 될 때까지 벡터를 넓히고 모두 INF 변수를 넣는다
0이라는 숫자를 만드는데는 당연히 0번이 쓰이기 때문에 0을 넣는다
아래에는 N번 반복한다, 위에서 0을 한번 넣었기 때문에 1부터 N 이하까지 해서 N+1에 모두 채운다
여기에서 a를 구해서 지금 현재 쓸 숫자의 제곱근의 내림을 구한다
예를 들어 N이 7인 경우를 구해보자면
i = 1인 경우
아직 a = 1이니까
dp[1]이랑 dp[0] + 1을 비교하면 당연히 1이 되고
i = 2인 경우에도
a = 1이니까
dp[2] = min(dp[2], dp[1] + 1)이니까 2가 되된다
i = 3인 경우에도
a = 1이네?
dp[3] = min(dp[3], dp[2]+1) 이니 3이고
i가 4인 경우에 j반복문이 한번 돌아간다
a = 2이니까
for문을 2번 돌려야한다
dp[4] = min(dp[4], dp[4-1]+1)
dp[4] = min(dp[4], dp[4-4] + 1)
이 2개를 돌리니까 dp[4]인 경우에는 1이 된다
이 모든 과정에서 j의 제한을 잡아주기 위해 a를 계속 업데이트해주는 개념이다
이렇게 하면 원하는 수까지 계속 숫자가 쌓이면서 제곱근이 있는 숫자라면 알아서 1로 다시 바꿔주고 다시 1씩 더하는 개념으로 진행한다
그러다가 예를 들어 8같이 4 4로 더해지는 수가 나타난다면
그것도 dp의 기능으로 2로 다시 만들어주는 개념으로 진행이 된다
결론적으로 dp에 제곱근만 빼면 되는 꽤나 간단한 문제였지만 아직 dp의 개념이 잘 잡히지 않아 수식 정의에 고민을 좀 했던 문제이다
