[성실코딩 31일차] 백준 #1699 제곱수의 합 ** / Knapsack

기말고사 시험공부 겸 Unbounded Knapsack문제를 찾아서 풀었다.

잘못된 접근 방식으로 풀어서 시간초과가 나왔고 ( 예제도 맞고 틀린 방법은 아니라고 생각함! 오래걸려서 비효율적일 뿐,,,,,)

그래서 맞은 사람 코드를 보고 공부했다.

• 옳은 풀이법 및 코드

참고 코드 링크 : http://wootool.tistory.com/102

이 코드에서 핵심 알고리즘

for (int n = 1; n <= N; i++)
    {
        for (int s = 1; s*s <= n; s++){   // s: square 1,4,9,16,25,...
            if (Dp[n] > Dp[n - s*s] + 1 || Dp[n] == 0) // DP 더 작은 값으로 update
                Dp[n] = Dp[n - s*s] + 1;
        }
    }

핵심 알고리즘 설명(풀이)

이 알고리즘을 이용해 DP Table을 채우면?

• 틀린 풀이법 및 코드

DP table을 채우는 방식에서 조금 오래 걸리게 푼거 같긴하지만

시간초과가 뜰줄이야!!!!!!!!!!!!!!!!!!!!!!

내가 오히려 더 복잡하게 문제를 풀어낸 것 같다,,,,어렵댱 ㅠㅠ

문제 풀이

구현에 필요한 변수(배열) - 제곱수를 저장하고 있는 square array, DP table인 m array

DP table을 채우는 공식

C언어 구현코드 (C++아님) - 시간초과

#include < stdio.h >
#include < stdlib.h > // malloc
#include < string.h > // memset

#define INF 987654321

int N; // 문제 자연수 N
int square[1000] = { 0, }; // 제곱수 저장해 놓는 배열. 
							// 사이즈 1000 <- N<=100,000 
							// 왜냐면 1000^2 = 1000000 > N(100,000)

// 자연수 _N을  제곱수들의 합으로 표현할 때
// 최소개수를 return
int getMinimumValue(int *_m, int _N) {
	
	int minimum_value = INF; // 반환값
	int new_value;

	int square_idx = 1;
	int square_cnt = 1;

	while (1) {
		// square배열 비어져있으면, 그 배열 채우기
		if (square[square_idx] == 0) {
			square[square_idx] = square_idx * square_idx; //제곱
		}
		// 탈출조건
		if (square[square_idx] > _N) {
			break;
		}	
		while (1) {
			// 탈출 조건
			if (square_cnt*square[square_idx] > _N) {
				square_cnt = 1; //초기화
				break;
			}
			new_value = square_cnt + _m[_N - (square_cnt*square[square_idx])];
			// minimum value update
			if (new_value < minimum_value) { 
				minimum_value = new_value;
			}
			if (square_idx==1) { // 1이면 square_cnt증가시키지 말고 while문 나가기 
				break;
			}
			// 1이아니면 square_cnt증가시키면서 확인하기
			square_cnt++;
		}
		square_idx++;
	}
	// 위의 조건 만족못해서 while에 못들어가고 확인 못함,,,,,
	if (minimum_value==INF) {
		// 아직 어떻게 처리해줘야할지 모르겠음
		printf("모든 조건 만족 못할 경우 _N = %d\n",_N);
	}
	return minimum_value;
}

int main(void) {

	// 문제 자연수 N 입력받기
	scanf("%d",&N); 
	
	// DP table 동적 배열 할당
	int *m = (int *)malloc(sizeof(int)*(N + 1)); // 초기화 필요 없을듯?
	m[0] = 0;

	// DP table 칸 채우기
	for (int i = 1; i <= N; i++) {
		m[i] = getMinimumValue(m, i);
	}

	printf("%d\n",m[N]);

	return 0;
}