백준] 1699 : 제곱수의 합

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

1699번: 제곱수의 합

 

 

 

 

접근 방법

문제를 풀면서 지금까지 풀었던 문제들과는 다르다는 것을 느꼈습니다.
수학적 + 논리적으로 점화식을 세워야 하기 때문에...
점화식 세우는 데 시간이 오래 걸린 문제였고, 아래 블로그를 많이 참고했습니다.

[출처] [백준] 1699 - 제곱수의 합| 작성자 occidere

- 큰 수의 제곱근부터 시작하는 것은 옳은 방법이 아닙니다.

- 만약 35가 주어졌다면,
 35를 만들어낼 수 있는 제곱수들은 1, 4(2^2), 9, 16, 25(5^2)로 총 4가지입니다.

이 수를 이용해 최소로 구성할 수 있는 방법은
[35 - 1 * 1], [35 - 2 * 2], [35 - 3 * 3], [35 - 4 * 4], [35 - 5 * 5]중 최솟값에서 + 1을 해준 값을 찾으면 됩니다.

=> 여기서 +1을 해주는 이유는, 제곱수 2를 가지고 예를 들어보면 43에서 2의 제곱인 4를 빼면 d[39]가 나온다.
이는 결국 39에 2^2를 더해서 43을 만들어 준다는 의미로, 39를 만드는 최소 제곱수의 항의 개수 + 1이 되는 것이다.

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

 

 

....

첫 번째 풀이 :

처음 접근 방법으로는 N이 주어졌을 때,

dp값을 구하기 위해 N....0까지 거꾸로 시작해서 구하는 방법이 더 쉬울 수 있다고 생각.

 

따라서 예제에 나온 11과 7의 경우 출력이 각각 3과 4로 나옴.

하지만,,

만약 n으로 15가 주어졌을 경우, 15 % i는 0이 되기 때문에 출력에 문제가 생김.

#include <iostream>
using namespace std;

int dp[100001];

int main() {
	int temp = 0, tempN = 0, n, result = 0;

	cin >> n;
	
	tempN = n;
	
	for(int i = 1; i <= n; i++){
		if(i * i <= n){
			temp = i;
		}
	}
	cout << "tempN : " << tempN << ", temp : " << temp << endl;
	
	for(int i = temp; i > 0; i--){
		if(tempN % i != 0){
			dp[i] += 1;
			tempN -= i * i;
			cout << tempN << endl;
			if(tempN <= 3){
				dp[i] += tempN;
			}
		}
	}
	
	//for(int i = temp; i > 0; i--){
	//	for(int j = 1; j <= temp; j++){
	//		if(tempN % i != 0){
	//			dp[i] += 1;
	//			tempN -= i * i;
	//	}
	//}
	//}
	
	for(int i = 1; i <= n; i++){
		cout << dp[i] << " ";
		result += dp[i];
	}
	
	cout << result;
	
	return 0;
}

 

 

정답 코드

#include <iostream>
using namespace std;

int dp[100001];
int Min(int a, int b){
	return a > b ? b : a;
}

int main() {
	
	int n;
	
	cin >> n;
	
	for(int i = 0; i <= n; i++){
		dp[i] = i;
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j * j <= i; j++){
			dp[i] = Min(dp[i - j * j] + 1, dp[i]);
		}
	}
	
	cout << dp[n];
	
	return 0;
}

 

 

 

 

참고한 블로그

[백준][1699번][DP] 제곱수의 합

[백준] 1699 - 제곱수의 합