[실2][C++] 백준 1699번 제곱수의 합 (dp)

1699번: 제곱수의 합 (acmicpc.net)

 

식을 어떻게 세워야 할지 고민하다가 세웠는데 시간초과 떴음. 근데 내가 세운것보다 훨씬 간단한 식을 써도 됐다. 시간 초과될 줄 알고 안했었는데 시간복잡도를 조금 더 생각해 볼 걸 싶었다. 그리고 배열에 negative index를 쓰면 0이 나온다. 쓰레기 값이 나올 줄 알았는데 다 0이 나와서 궅이 j를 root 까지 계산해 줄 필요 없이 root자리에 i를 써도 될것같다. 

 

내 코드

#include <iostream>
#include <cmath>

using namespace std;

const int MAX = 100001;

int dp[MAX];

int main() {
	int n;
	cin >> n;

	int root;

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

	cout << dp[n];

	return 0;
}

 

+ 못풀었다!!.. 그치만 오늘 못풀었으니까 다음엔 풀겠지. 그리고 이제 dp 절대 안까먹을듯

 

참고

[ 백준 1699 ] 제곱수의 합 (C++) :: 얍문's Coding World.. (tistory.com)