[백준] 1699번 제곱수의 합 (C++) - dynamic programming

문제

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

1699번: 제곱수의 합

코드

#include <iostream>

using namespace std;

int dp[100001] = {0};

int main(){
  int n;
  cin >> n;
  for(int i=1; i<=n; i++){
    dp[i] = i;
    for(int j=1; j*j<=i; j++){
      if(dp[i] > dp[i-j*j]+1){
        dp[i] = dp[i-j*j] + 1;
      }
    }
  }

  cout << dp[n];
  return 0;
}

정리

쭉 나열해본다음 제곱수에서 규칙을 찾겠다는 생각이 들었지만 끝내 스스로 코드로 구현을 하지 못해 다른 사람 코드를 참고했다. 이중 for문을 이용하고 dp[i-j*j] 방식으로 제곱수를 빼는 방식으로 구현했다. dp에서 규칙 찾는 연습을 더 열심히 해야겠다. 

참조

https://guiyum.tistory.com/17