백준 1699 제곱수의 합 c++ // dp 2차원 to 1차원, 수학으로 시간복잡도줄이기

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

1699번: 제곱수의 합

0. 시행착오

1. dp[104]로 선언해놓고 for(int i=0~104)로 초기화 -> out of bound...

2. 2중for문 100000 * 100000 으로 해놓고 왜안됨? 뻘짓..

 

1. 수학으로 시간복잡도줄이기

문제 : i의 범위 100000 * j의 범위 100000 -> 시초

해결 : i의범위는 root n <n / root 4 < 4 이므로 i는 root n까지만 탐색해도된다.

 

2. 의사코드

초기화 : 초록형광색부분을 초기값으로 초기화한다.

j행에 1~target을 놓고

i행에 주머니, 코인등을 추가시키면서 규칙성(화살표)을찾는다.

dp = min(위쪽, dp[j-i])임을 발견한다.

 

3. dp 2차원 to 1차원

위쪽을 확인하는 것은 자기자신을 확인하는것과 같다. //위쪽확인대신 자기자신을 확인하면 된다.

dp[i-1][j] == dp[j]

 

3. 전체코드

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int n,dp[100004];


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

	cin >> n;
	

	//dp[i][j] : i자연수 추가시 j를만드는 행의 최소갯수
	for (int j = 1; j < 100000; ++j) dp[j] = j;

	for (ll i = 2; i*i <= n; ++i) {
		ll a = i * i;
		for (int j = 1; j <= n; ++j) {
			if (j - a >= 0) {
				dp[j] = min(dp[j], dp[j - a] + 1);
			}
			/*else
				dp[j] = dp[j];*/

		}
	}
	
	/*for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			cout << dp[i][j]<<" ";
		}
		cout << "\n";
	}*/

	cout << dp[n];

	return 0;
}

 

4. 추가개선

j-a가 음수인 범위는 사실상 위쪽을 그대로 가져다 씀 -> j를 a(i*i)부터 시작하면

20%의 시간단축이 있다.