백준 1699 제곱수의합

//두번째로 짰던 코드
#include<stdio.h>

int n;
int sqr[1001];
int dp[100001];

int init(){
	
	scanf("%d", &n);
	
	int idx;
	for(int i=1; (i-1)*(i-1) <= n; i++){
		sqr[i] = i*i;
		idx = i;
	}
	
	return idx;
}

int main(){

	//제곱수 sqr배열에 저장. 
	int idx = init();
	
	//dp 초기값
	dp[1] = 1;
	
	//2부터 n까지. 
	 for(int i=2; i<=n; i++){
	 	
	 	int N = i;
	 	
	 	int k;
	 	for(k=1; k<=idx; k++){
	 		if(sqr[k] > N){
	 			k = k-1;
	 			break;
			}
		}
		
		N -= sqr[k];
		dp[i]++;
		dp[i] += dp[N];	
		
		
		N = i;
		k--;
		N -= sqr[k];
		if(dp[N] != 0 && dp[N] + 1 < dp[i]){
			dp[i] = dp[N] + 1;
		}
		
		
	}
	
	printf("%d", dp[n]);

	return 0;
}

 실버3짜리 dp문제다. 약 3번 트라이후, 방향을 잘못 잡고 있나 싶어서 다른 블로그의 글을 보고 풀었다.

chanhuiseok.github.io/posts/baek-10/

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

문제점 : 

1. 첫번째 시도에서 틀렸다. 반례를 찾았다. 22와 같이 'n보다 작은 자연수 중 가장 큰 제곱수'를 항상 빼버리면 

22 = 16 + 4 + 1 + 1

22 = 9 + 9 + 4 와같이, 정답을 못 구하게 된다.

여기서 착안하여, 'n보다 작은 자연수 중 가장 큰 제곱수 - 1'을 구해서 더 작은 경우 dp값을 업데이트 하는 방법을 썼는데, 당연히 틀렸다. 여기서 갑자기 이상한데로 헤매기 시작했다. 아니, 어느정도 방향은 맞았는데 너무 복잡하게 하고있었다. 재귀함수를 이용하여 top-down식으로 풀었는데, 똑같은 연산을 계속하곤 했다. 사실 여기서 잘못되었다는 것을 눈치챘어야 했는데..

 

이번 문제를 통해 나름 얻은게 많았다. dp에 대해 더 감이 잡힌듯하다. 잘게 잘게 나누기,, '같은연산'을 반복하는 이유를 파악하고, 해결하기... top-down으로 풀고있는지 한번 의심해보기 등등.. ㅎ

 

 

//헤메던 3번째코드 - top down - 같은연산반복
#include <stdio.h>

int sqr[100000];
int min = 1000000000;

void init(int n) {
    for (int i = 1; i <= n; i++) {
        sqr[i] = i * i;
        if (i * i > n) break;
    }
}

int findIdx(int n) {
    int largest = 1;
    for (int i = 1; i <= (n / 2 + 1); i++) {
        if (i * i > n) {
            largest = i-1; //idx = n보다 같거나 작은 가장 큰 제곱수 
            break;
        }
    }
    return largest;
}

void socrates(int n, int i, int d) {

    if (d > min) return; //d means depth

    n -= sqr[i];
    if (n == 0) {
        if (d < min) {
            min = d;
        }
        return;
    }

    int largest = findIdx(n);
    for (int k = largest; k >= 1; k--) {
        socrates(n, k, d + 1);
    }
}



int main() {

    int n;
    scanf("%d", &n);

    init(n);

    int largest = findIdx(n);

    for (int i = largest; i >= 1; i--) {
        socrates(n, i, 1);
    }

    printf("%d", min);

    return 0;
}

 

// 블로그 보고 풀이한 깰끔 bottom - up 코드
#include<stdio.h>
#define min(a,b) a>b ? b : a

int n;
int sqr[1001];
int dp[100001];

void init() {

	scanf("%d", &n);

	for (int i = 0; i <= n; i++) {
		dp[i] = i;
	}
}

int main() {

	//제곱수 sqr배열에 저장. 
	init();

	//dp 초기값
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;

	//2부터 n까지. 
	for (int i = 4; i <= n; i++) {
		for (int k = 2; k * k <= i; k++) {
			dp[i] = min(dp[i], dp[i - k * k] + 1);
		}
	}

	printf("%d", dp[n]);

	return 0;
}