개요

[링크]백준 1669번: 제곱수의 합

• 입력
  첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

• 출력
  주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

접근 방식

• 바텀업 방식
  dp배열에 타깃값이 i일 때 사용하는 동전의 최소갯수를 저장한다.
  각 i에서 dp[i]에는 최대값인 i를 저장해준 뒤,
  i보다 작은 변수 j를 설정 후 (j의 범위는 1부터 루트 i까지)
  dp[i]= min(dp[i],dp[i-j^2]+1)으로 잡아준다.
  풀어 말하자면 각 제곱수를 뺀 값에서 1을 더했을 때 값과 dp[i]값과
  계속 비교하는 방식이다.

• 탑다운 방식
  dp배열의 행은 타겟값, 열에는 몇 번째 수인지를 저장한다.
  square배열에는 제곱수를 미리 다 저장한다.
  그 후 방식은 [동전 2] 방식과 유사하다.

  solution함수에는 타겟값과 몇 번째 제곱수인지 나타내는
  n을 매개변수로 넘겨준다.
  타겟값이 0이라면 0을 return,
  n이 마지막 값이면 n을 return 해준다. ( 위 바텀업 방식과 유사하게 최대값은 n으로 넣어주는 방식.)
  ret값에 dp배열 값을 참조시킨 후, 이미 구한 값이면 해당 값 return해준다.
  아니라면 solution(target,n+1)을 넣어준다.
  그 후, solution(target,n+1)값과 solution(target-square[n],n)+1값중에 더 작은 값을 ret에 넣어준다.
  

바텀업 방식 코드

#include<iostream>								//3
												
#include<algorithm>

//n번째 값에서 k^2
int dp[100'000], amount = 0;
using namespace std;

void input() {
	cin >> amount;
}

//바텀업 방식
void solution() {
	for (int i = 1; i <= amount; i++) {
	//각 dp[i]값엔 최대값인 i를 넣어준다.(1^2 i번 더했을때가 최대값 )
		dp[i] = i;
		//1부터 j*j<i를 만족하는 j값까지 dp[i]값과, dp[i-j*j]+1 값을 비교해서 저장(여기서 동전 2의 방식이 나옴 해당 값을 빼고 +1을 하는 방식)
		for (int j = 1; j*j <= i; j++) {
			dp[i] = min(dp[i], dp[i - j * j] + 1);
		}
	}
	cout << dp[amount];
}

int main() {
	input();
	solution();
}

탑다운 방식 코드

//제곱수들을 다 만든 후 동전2 의 방식과 같은 탑다운 방식 

#include<iostream>
#include<algorithm>

using namespace std;
const int MAX = 317;
int square[MAX], dp[100'001][MAX],amount=0;

void input() {
	cin >> amount;
	for (int i = 0; i < MAX; i++) {
		square[i] = i * i;
	}
}

//탑다운 방식, n번째 제곱수를 이용해 target값을 만들기
int solution(int target, int n) {
	//만약 입력받은 값을 계속 줄여나가다가 0이나오면 0
	if (target == 0) return 0;
	//만약 위치값이 끝까지 가면 n을 return
	if (n == MAX - 1) return n;
	//ret값에 해당 dp값 참조시켜준다.
	int& ret = dp[target][n];
	//ret값이 이미 있을 경우 바로 return
	if (ret) {
		return ret;
	}
	ret = solution(target, n + 1);
	//ret값은  n+1에 해당하는 제곱수부터 target값을 만드는 경우의수와
	//n번째 제곱수를 하나 사용한 후 target-square[n]의 값을 만드는 경우의 수와 비교
	if(square[n]<=target) ret = min(ret, solution(target - square[n], n) + 1);
	return ret;

}

int main() {
	input();
	cout<<solution(amount, 0);
}

문풀후생

처음에 탑다운방식에서 배열을 대충 생각해서 타깃값은 최대 10만,
숫자를 400으로 잡았더니 당연히 1억 6천만 바이트가 되서 160메가가 넘어서 메모리초과가 되었다. 그래서 어떻게 구현할까 하고 뒤져보다
정확히 317로 잡으면 130메가로 아슬아슬하게 통과를 받았다.
그리고 동전 2유형의 문제에서 탑다운 방식을 쓸 때,
지금 더하려는 값을 뺀 값+1과 지금 값을 비교하는게 잘 생각이 안난다.
더 많이 풀어봐야겠다.

레퍼런스

[탑 다운 방식 ]https://github.com/kks227/BOJ/blob/master/1600/1699.cpp