[코드트리] 제곱수의 합으로 나타내기

 

 

---

 

문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

개념

DP

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int sol(int n) {
  vector<int> dp(n + 1, 5000);
  dp[0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j * j <= i; ++j) {
      dp[i] = min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
}

int main() {
  int n;
  cin >> n;
  cout << sol(n) << endl;
  return 0;
}

 

 

 

 

코드 설명

최소 개수의 제곱수 합으로 표현하기 위한 최소 제곱수의 수를 저장하는 dp 배열을 선언한다.

최소 제곱수를 계산해야하므로 문제에서 최대 범위로 주어진 5000으로 초기화한다.

j를 각 제곱수라고 하면, j를 제곱하여 i보다 작거나 같은 모든 경우의 수를 고려한다. 
이때 j가 0일때는 0이므로 제외하고 1부터 2,3.. 하나씩 수를 늘려가며 조건을 만족할 때까지 최소 개수를 구한다.

예를 들어 i = 12라면 

dp[12 - 1^2] + 1 = dp[11] + 1
dp[12 - 2^2] + 1 = dp[8] + 1
dp[12 - 3^2] + 1 = dp[3] + 1 

따라서 최솟값은 dp[12] = 3이다.

 

 

 

 

---