[백준 17626] Four Squares (C#, C++) - soo:bak

문제 링크

17626번 - Four Squares

설명

자연수 n을 최소 개수의 완전제곱수의 합으로 나타내는 문제입니다.

라그랑주의 네 제곱수 정리에 따르면 모든 자연수는 네 개 이하의 완전제곱수의 합으로 표현할 수 있습니다. 예를 들어 25 = 5², 26 = 5² + 1², 27 = 3² + 3² + 3²입니다.

주어진 자연수 n을 완전제곱수의 합으로 표현할 때 필요한 제곱수의 최소 개수를 구해야 합니다.

n은 1 이상 50,000 이하입니다.

접근법

작은 수의 답을 이용하여 큰 수의 답을 구하는 동적 프로그래밍으로 해결합니다.

dp[i]를 i를 만드는 데 필요한 최소 제곱수 개수로 정의합니다.

dp[1] = 1, dp[4] = 1 (2²), dp[5] = 2 (4 + 1)처럼 작은 수부터 차례로 계산합니다.

각 수 i에 대해 초기값을 dp[i] = i로 설정합니다. 이는 1²만 사용하는 최악의 경우입니다.

i보다 작거나 같은 모든 제곱수 j²를 시도하여 최솟값을 찾습니다.

이 때, dp[i - j²]는 이미 계산되어 있으므로 dp[i - j²] + 1로 갱신할 수 있습니다.

예를 들어 dp[13]을 계산할 때 dp[4] = 1을 이미 알고 있으므로 dp[13] = dp[4] + 1 = 2 (9 + 4)가 됩니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var dp = new int[n + 1];

      for (var i = 1; i <= n; i++) {
        dp[i] = i;
        for (var j = 1; j * j <= i; j++) {
          var sq = j * j;
          dp[i] = Math.Min(dp[i], dp[i - sq] + 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, 0);

  for (int i = 1; i <= n; ++i) {
    dp[i] = i;
    for (int j = 1; j * j <= i; ++j)
      dp[i] = min(dp[i], dp[i - j * j] + 1);
  }

  cout << dp[n] << "\n";

  return 0;
}