백준 1699 제곱수의 합

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

어떤 수 n을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제

 

처음 접근 방식

1. 무식하게 접근

n=11이라고 했을 때

for문 하나를 돌면서 n보다 작으면서 가장 큰 제곱수 k를 찾는다 3^2=9니까 k=3

while문을 n>0이고 k!=0일 때까지 돌면서 n에서 k^2을 뺄 수 있을 때까지 뺀다

뺄 수 없다면 k--로 넘어간다

이 방법을 재귀로 바꾼다

 

2. 재귀로 완전 탐색

이런 식으로 돌면서 cnt로 항을 세면 됐다

이 재귀를 DP로 바꾼다

 

3. DP로 변환

근데 여기서 막혔다

로직은 k가 1부터 올라가면서, m에 합을 저장하고 dp[k][m]은 합이 m일 때의 항의 최소 개수로 뒀다

(그림에서는 a가 있지만 잘못씀)

 

그래서 DP를 채우는데, 

1. 수가 들어갈 수 없다면 항 하나 추가하고 k++

2. 수가 들어갈 수 있다면 min(그 수를 추가, ..?)

이러면 1만 계속 들어가게 되니까 잘못되었다

 

게다가 이 방법의 가장 큰 문제점

만약 12가 있다면 12보다 작은 최대 제곱수가 3(3^3=9)이니까

12=3^2+1^2+1^2+1^2 해서 4보다

12=2^2+2^2+2^2 해서 3이 정답이다

그러므로 최대 제곱수를 구하는 거 부터 잘못되었다

아예 시작부터 에러였다

 

다른 접근 방법

어차피 k가 올라가면서 제곱수를 만들거면 k를 굳이 뺄 필요가 없었다

그냥 k가 1~n까지 올라가면서 이 수로 졔곱을 만들 수 있나를 확인하면 됐다

 

아까 DP[k][m]에서 k를 빼서 DP[i] 하나만 둔다

그러면 DP[i]는 i일 때 만들 수 있는 가장 적은 항 개수를 담는 배열이됨

 

이제

1. 1^2로만 그 수를 만들었을 때랑

2. 제곱수가 있다면 제곱수로 만들 때랑 더 작은 수를 저장할 거임

 

근데 사실 1^2로만 만든 수는 제곱수가 없는 낮은 숫자들만 해당되는 거고

제곱수가 하나라도 있다면 그걸 쓰는 게 이득인데 굳이 저렇게 하는 이유는 2번을 비교해주기 위해서임

 

그럼 2번은 무슨 말이냐면 만약 n=12라면 12를 만들 수 경우를 전부 비교해서 그 중에 가장 적은 항을 dp[i]로 한다는 말

제곱이 되는 수들을 다 비교해주는 이유는

n=12라면 가능한 조합은

2^2+2^2+2^2

3^2+1^2+1^2+1^2

1^2 12번 중에 최소를 구해야 하기 때문이고,

 

2^2+2^2+2^2는 DP[8]+2^2 (DP[8]=2^2+2^2니까 2)

3^2+1^2+1^2+1^2은 DP[3]+3^2 (DP[3]=1^2+1^2+1^2니까3)

이런 식으로 그 전에 제곱수에+a를 한 값을 보는 거니까 DP[i-j*j]+1이 된다

풀어쓰자면 i(현재 만들 수)-j*j(2부터 1씩 증가하는 제곱이 되는 수)+a에 대한 +1값 더함

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

int main() {
	ios::sync_with_stdio(0); cin.tie(NULL);
	int n, dp[100001];
	cin >> n;
	for (int i = 0; i <= n; i++) dp[i] = i;
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j * j <= i; j++) {
			dp[i] = min(dp[i], dp[i - j * j] + 1);
		}
	}
	cout << dp[n];
}

DP[0]도 접근해야 할 수도 있기 때문에 0부터 초기화 해야 함