[C++] 백준 7579 - 앱 (동적 계획법, 메모이제이션)

0. [c++] 백준 - 7579

https://www.acmicpc.net/problem/7579

1. 풀이

오래간만에 동적 계획법을 활용하려 하니 시간이 오래 걸린 문제였다.

이 문제를 풀기 위해서 필요한 포인트는 무엇인가?

메모이제이션을 어떻게 잡느냐가 가장 중요한 포인트였다.

가장 처음 시도는 cache[i][j]로, i~j사이에서 M의 메모리를 넘기는 최소 cost를 저장하도록 계획하고, 최소 cost가 존재하지 않으면 INF값을 넣을 계획이었는데, 생각보다 구현이 쉽지 않았다.

그래서 다른 방법을 찾아보았는데, cache[i][j] = i번에서 j만큼의 cost로 만들 수 있는 최대 메모리를 저장하는 것이었다.

이러한 방법을 활용해 문제를 해결해보았습니다.

1. 우선 메모이제이션을 활용하기 위해 cache를 -1로 초기화

2. 동적 계획법을 활용해 탐색이 중복되지 않도록 해준다.

2. 소스코드

#include<iostream>
#include<algorithm>
#include<cstring>        //memset
 
using namespace std;
 
int N, M;
 
int memory[100];
int cost[100];
//cache[i][j]는 i위치부터 j비용으로 만들수 있는 최대 메모리 크기
int cache[100][10001];
 
int calc_memory(const int& here, const int& total_cost) {
    if (here >= N)
        return 0;
    
    //메모이제이션 활용
    int& ret = cache[here][total_cost];
 
    //기저 사례 : 이미 탐색이 완료된 경우
    if (ret != -1)
        return ret;
 
    //현재 앱을 비활성화 시키지 않은 경우
    ret = calc_memory(here + 1, total_cost);    
 
    //현재 앱을 비활성화 시키는 경우
    if (cost[here] <= total_cost)
        //현재 앱을 비활성화 시키지 않은 경우와 비교하여 더 큰 메모리를 선택
        ret = max(ret, memory[here] + calc_memory(here + 1, total_cost - cost[here]));
    
    return ret;
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++)
        cin >> memory[i];
    for (int i = 0; i < N; i++)
        cin >> cost[i];
 
    //메모이제이션을 활용하기 위해 초기화
    memset(cache, -1, sizeof(cache));
 
    int ret = 0;
 
    //가능한 최대 코스트는 10000까지 탐색을 진행하도록 하자.
    for (int i = 0; i < 10001; i++) {
        ret = calc_memory(0, i);
        if (ret >= M) {
            cout << i;
            break;
        }
    }
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!