[PS 백준 - 5.8] 1699번: 제곱수의 합

문제 정보

백준 1699번 - 바로가기

• 난이도: 실버 3
• 알고리즘: 다이나믹 프로그래밍

---

코멘트

이 문제는 5.3 동전 2 문제에서 동전 값들이 제곱수로 바뀐 문제다. 이 때 k의 상한선이 10만 즉, $316<\sqrt{100000} <317$ 이므로 배열 squares의 크기는 $317$ 로 선언해두었다.

• [Parameters]
  • n: 제곱수 순서
  • k: 나타낼 숫자
• [base case]
  • 제곱수를 다 쓰고난 후 나타낼 숫자가 1이면 k 리턴
• [Logic]
  1. squareNum 함수는 n번째 제곱수부터 사용할 때 k를 나타내는 제곱수의의 최소 개수를 리턴해야 한다.
  2. n번째 제곱수가 사용이 불가능할 경우 다음 제곱수를 고려하는 함수로 넘어간다. -> int result = squareNum(n + 1, k);
  3. n번째 제곱수가 사용 가능할 경우 결과는 (k를 유지하고 다음 제곱수로 넘어간 경우) 와 (k가 감소하고 이 제곱수를 사용한 경우) 중에서 제곱수를 최소로 사용한 결과를 리턴하면 된다.

---

소스 코드

<탑다운 방식>

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

int squares[317]; // 317^2 > 100,000
int dp[317][100001]{ 0, };
int N;

// n: 제곱수 순서 / k: 나타낼 숫자
int squareNum(int n, int k) { 
	// base case
	if (squares[n] == 1) return k;

	// memoization
	if (dp[n][k] != 0) return dp[n][k];

	int result = squareNum(n + 1, k);

	// 제곱수보다 클 경우:
	if (k >= squares[n]) {
		result = min(squareNum(n + 1, k), squareNum(n, k - squares[n]) + 1);
	}

	// dp 기록 갱신
	dp[n][k] = result;
	return result;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	int x = (int)(sqrt(n));


	for (int i = 0; i < x; i++) {
		squares[i+1] = (x-i) * (x-i);
		//cout << i+1<<": " <<squares[i+1] << endl;
	}
	cout << squareNum(1, n);
}

---

<바텀업 방식> - by zzoni

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

int dp[100001];

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
        dp[i] = i;

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

    cout << dp[n];
    return 0;
}