[백준 1699] 제곱수의 합 (C#, C++) - soo:bak

문제 링크

1699번 - 제곱수의 합

설명

주어진 자연수 N을 제곱수들의 합으로 표현할 때, 필요한 제곱수 항의 최소 개수를 구하는 문제입니다.

접근법

동적 프로그래밍으로 해결합니다. 각 수에 대해 그 수를 만들기 위한 최소 제곱수 개수를 저장합니다.

어떤 수 i를 만드는 방법은 i보다 작은 제곱수 k의 제곱을 빼고 나머지를 최적으로 만드는 것입니다. 따라서 i에서 가능한 모든 제곱수를 빼본 뒤, 나머지를 만드는 최소 개수에 1을 더한 값 중 최솟값을 선택합니다.

초기값으로 각 수를 1의 제곱 합으로만 표현한다고 가정하면, i를 만드는 데 i개가 필요합니다. 이후 더 큰 제곱수를 사용하면서 이 값을 줄여나갑니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var dp = new int[n + 1];
    for (var i = 1; i <= n; i++) {
      dp[i] = i;
      for (var k = 1; k * k <= i; k++)
        dp[i] = Math.Min(dp[i], dp[i - k * k] + 1);
    }
    Console.WriteLine(dp[n]);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi dp(n + 1);
  for (int i = 1; i <= n; i++) {
    dp[i] = i;
    for (int k = 1; k * k <= i; k++)
      dp[i] = min(dp[i], dp[i - k * k] + 1);
  }
  cout << dp[n] << "\n";

  return 0;
}