카드 구매하기 11052

카드 구매하기 (11052)

해설

---

적용한 레시피 / 방법론 + 접근법

메모이제이션 구현 패턴

굉장히 자주 접하게 될 메모이제이션은 한 가지 패턴을 정해두고 항상 같은 형태로 구현 하면 버그를 찾기도, 작성하기 도 쉬워집니다.

1. 항상 기저 사례를 먼저 처리합니다. 입력이 범위를 벗어난 경우 등.

2. cache 를 초기화합니다. -1로 할지 numeric_limits 로 할지 등은 문제에 따라 정합니다.

3. ret 가 cache 의 참조형으로 사용된다. 고차원 배열에서의 인덱스 실수를 없애준다.

4. 메모이제이션용 배열을 초기화하는 방법을 알아두자. 정수형일 경우 memset 이 도움된다.

메모이제이션 시간 복잡도 분석

주먹구구식으로 이를 짐작해봅시다.

(존재하는 부분 문제의 수) x (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

이러한 방식으로 수행 시간의 상한 을 짐작해 볼 수 있다.

풀이

1. 마지막의 카드팩에는 몇 번째 카드팩일까?

- 모른다. 다이나믹에서 아주 중요한 정보이다. 1번째? 2번째, 알 수 없다. 모든 방법을 다 해봐야 한다. 1번째 카드팩인 경우부터, N번째 카드팩인 경우 까지 있을 것이다.

2. 재귀 ? 반복문?

- top down 방식인 재귀문이 나에게는 더 친숙하기에 재귀로 접근하였다. (항상 기저사례를 생각하고, 정해진 틀대로 움직이려고 한다. 위의 메모이제이션 레시피 (종만북) 이 점차 익숙해졌다.)

- 점화식을 재귀문으로 구현해보았다.

int solve(int count){
	// 기저 사례 : 1 개 카드를 사는 지점은 return
	if(count == 1) return cache[1];
	
	int& ret = cache[count];
	
	// p_count 의 카드팩을 1개 구입하는 것을 기본 값으로 두고
	ret = p[count];
	
	// 점화식으로 비교해나감
	for(int i = 1; i < count; i++){
		ret = max(ret, (solve(count - i) + p[i]));
	}
	
	return ret;
}

결과는 시간초과. 문제의 시간 복잡도를 생각해보면 (존재하는 부분 문제의 수) x (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수) = N x N 이므로 O(N^2) 이다. 최대 N이 10,000 이므로 100,000,000 이다. 

이러한 부분을 메모이제이션으로 해결할 수 있다. 기존에 계산했던 cache 의 값들을 이용하는 것이다. 이를 통해 중복 계산을 줄인다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 11052 카드 구매하기
const int MOD = 10007;
const int INF = -123456789;
int n;
int p[10001];
// cache : 카드 n 개를 사는 최댓값을 저장한다.
int cache[10001];

int max(int a, int b){
	return a > b ? a : b;
}

int solve(int count){
	// 기저 사례 : 1 개 카드를 사는 지점은 return
	if(count == 1) return cache[1];
	
	int& ret = cache[count];
	
    // 메모이제이션
	if(ret != INF) return ret;
	
	// p_count 의 카드팩을 1개 구입하는 것을 기본 값으로 두고
	ret = p[count];
	
	// 점화식으로 비교해나감
	for(int i = 1; i < count; i++){
		ret = max(ret, (solve(count - i) + p[i]));
	}
	
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n;
	fill_n(cache, 10001, INF);
	for(int i = 1 ; i <= n; i++) cin >> p[i];
	
	// 한 개의 카드를 사는 최댓값은 p[1] 과 같다.
	cache[1] = p[1];
	
	cout << solve(n) << '\n';
	
	
	
}

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점