[👊DP뿌시기 #16] (BOJ 1699) 제곱수의 합

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

---

접근법

어떤 수 N에 대해서 가장 적은 제곱수의 합은 무엇이 있을까?

N-(1*1)에서 1*1가 더해진 경우
N-(2*2)에서 2*2가 더해진 경우
N-(3*3)에서 3*3가 더해진 경우

이런식으로 N-(j*j)가 0일때까지의 경우가 있을 것이다.

 

우리는 가장 적은 항으로 표현한 제곱수 합을 구해야한다.

따라서, 다음과 같이 표현할 수 있다.

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

 

이런식으로만 코딩을 하면 0이 도출된다.

왜냐하면, 전역변수로 선언해서 기본값이 0으로 설정되어있기때문이다.

그렇기 때문에, 기본값을 초기화해야한다.

어떤 값으로 초기화해야할까?

가장 많은 항의 개수로 초기화하면된다.

가장 많은 항이 되려면 무조건 1로만 이루어져야 하기 때문에

DP[i] = i로 초기화하면된다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#define MAX 100001

using namespace std;

int n,t;
int dp[MAX];

void init() {
	for (int i = 1; i <= n; i++)
		dp[i] = i;
}

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

	cin >> n;
	init();

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

	cout << dp[n];
}