백준 7579번 앱

문제 링크입니다: https://www.acmicpc.net/problem/7579

처음에는 가격을 기준으로 인덱스와 총 메모리양으로 메모이제이션을 시도하다가 메모리 초과로 실패했던 문제였습니다.

100문제를 넘게 풀었지만 여전히 메모리 초과 에러는 컴파일해야지만 알 수 있는 초보는 웁니다 ㅠㅠ

그 다음에도 여전히 가격을 기준으로 인덱스와 총 가격으로 메모이제이션을 시도해서 테스트 케이스까지는 맞았지만 시스템 케이스에서 틀려 왜맞틀 문제가 되었습니다.

두 번째 시도까지 틀리고 곰곰히 생각해보니 확보할 메모리양이 정확히 M이 아니라 M 이상이라는 것을 파악했습니다.

확보해야할 메모리 양이 M 이상이기 때문에 총 메모리양을 기준으로 인덱스와 가격으로 메모이제이션을 진행한 다음,

총 가격을 순차적으로 증가시키면서 최초로 M 이상이 나오는 가격을 찾으면 되는 문제였습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100;

const int MAXCOST = 10000 + 1;

 

int N, M;

int memory[MAX];

int cost[MAX];

int cache[MAX][MAXCOST];

 

//메모리를 메모이제이션(10,000,000 너무 크다)

int maxMemory(int idx, int totalCost)

{

        //기저 사례: 범위 초과 시

        if (idx >= MAX)

                 return 0;

 

        int &result = cache[idx][totalCost];

        if (result != -1)

                 return result;

       

        result = maxMemory(idx + 1, totalCost); //해당 앱 비활성화 안 시켰을 경우

        //totalCost보다 해당 인덱스에 있는 앱의 비활성화 가격이 같거나 작다면

        //비활성화 안 했을 때와 비활성화 했을 때와 비교해서 메모리가 더 큰 쪽 선택

        if (cost[idx] <= totalCost)

                 result = max(result, memory[idx] + maxMemory(idx + 1, totalCost - cost[idx]));

        return result;

}

 

int main(void)

{

        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 totalCost = 0;

        //0부터 시작해서 최초로 M 바이트 이상 확보 시 답 찾음

        while (1)

        {

                 if (maxMemory(0, totalCost) >= M)

                 {

                         cout << totalCost << endl;

                         break;

                 }

                 totalCost++;

        }

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~