[백준] 1699번 제곱수의 합 C++ 코드

코드

#include <iostream>
#include <algorithm>

using namespace std;
const int INF = 987654321;
int n, a[100003];

int main() {
  cin >> n;
  fill(a, a + 100003, INF);
  a[0] = 0;
  for(int i = 1; i < n + 1; i++) {
    for(int j = 1; j*j <= i; j++) {
      a[i] = min(a[i], a[i - j*j] + 1);
    }
  }
  cout << a[n] << '\n';
  return 0;
}

최소값을 찾아야하므로, 배열을 매우 큰 값으로 초기화한다. 그리고 배열을 돌면서 해당 배열보다 작으면서 제곱수를 포함하고 있는 것들 중 최소를 찾고, 제곱수의 개수를 1개 더한 값과 비교해서 최소값을 찾으면 된다.