백준 1699 - 제곱수의 합 (c++)

백준 1699 - 제곱수의 합

문제 링크

생각 및 접근

• dp[i]
  • i를 제곱수의 합으로 나타내었을 때 가질 수 있는 항의 최솟값을 저장한다.
• 우선, dp[i]의 최솟값은 i가 제곱수일 때이므로 1이다. 필자는 cnt라는 변수를 사용해 내가 검사하려는 i가 제곱수인지 판별하였다.

    if (i == cnt * cnt) {
        dp[i] = 1;
        cnt++;
    }

• i를 제곱수의 합으로 나타낼 때 가질 수 있는 항의 최솟값을 구하기 위해서는 일단 제곱수가 많을수록 유리하다. 따라서 제곱수가 하나 있다고 생각하고 j-for문을 돌렸다.
  • 18 = 16 + 1 + 1 = 9 + 9 인 경우도 있으므로, j-for문을 돌렸어야 했다.

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

코드

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

int n, cnt = 1, dp[100001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        if (i == cnt * cnt) {
            dp[i] = 1;
            cnt++;
        }
        else {
            dp[i] = 2147000000;
            for (int j = 1; j <= cnt - 1; j++) {
                dp[i] = min(dp[i], 1 + dp[i - j * j]);
            }
        }
    }

    cout << dp[n];
}

채점 결과