백준 - 7579번 앱

문제

앱을 비활성화 하는 데 소모되는 cost, 확보할 수 있는 memory가 주어질 때
원하는 만큼의 memory 확보를 위해 소모되는 최소 cost를 구하시오

생각

memory는 주어진 값들의 크기, 합쳐져서 만들어 질 수 있는 값이 cost보다 크고,
예전에 풀었었던 기억도 있고 그래서

앞에서부터 돌면서 이 아이를 사용하며
cost 별 확보 할 수 있는 최대 memory를 저장해서
문제를 풀어야한다는 생각이 들었다

ex)

5 60
35 40 30 10 20
5 4 3 0 3가 input 일 때

첫번째 35, 5를 보고
maxMem[5]=35 //cost 5로 35 확보 가능!

두번째 40, 4를 보고
maxMem[9]=75 //maxMem[5]=35를 보고 cost 4, mem 40 도 사용해 cost 9로 75 확보 가능!
maxMem[4]=40

세번째 30, 3을 보고
maxMem[8]=65 //maxMem[5]=35를 보고 ''
maxMem[12]=105 //maxMem[9]=75를 보고 ''
maxMem[7]=70 //maxMem[4]=40를 보고 ''
maxMem[3]=30

점화식을 세워보면 maxMem[j+cost[i]] = max(maxMem[j] + mem[i] , maxMem[j+cost[i]])

어떻게 하더라

코드 구현 방법 기억이 안 났던 부분이 2가지 있었다.

1.maxMem[]으로 어떤 자료 구조? 어느 정도 크기? 값을 언제 추가?

나는 항상 벡터보단 배열에 먼저 손이 가는 편인데
벡터가 좋은 상황에선 벡터를 쓰는 버릇이 들면 좋을 것 같아서
처음엔 벡터를 써야하나.. 생각했는데,

앞에서 부터 순서대로 탐색 시 총 사용한 cost 합이 1,2,3,, 순서대로 증가하지 않아서
배열을 사용해서 특정 index 값에 접근해야겠다고 생각함.

배열 크기를 어떻게 지정하냐도 고민이였는데,
가능한 최대 cost의 크기가 100이고, 주어지는 최대 cost의 수도 100이니까
10000 정도 크기의 배열을 만들어주면 되더라,,

2.어느 어느 cost들을 사용해서 만들어진 값인지 어떻게 알더라?

처음엔 아 set을 가지고 다니면서 누구누구를 사용해서 만들어진 cost에요
앞으로 나머지 애들만 더해서 구해주세요
이렇게 구현해야하나 했는데,

//그냥 앞에서 부터 순서대로 돌면서
for (int i = 0; i < n; i++) {
    for (int j = 지금까지 돌면서 만들 수 있는 최대에서부터; j > 0; j--) {
    	//지금까지 만들어 낸 정보가 담긴 배열을 만나면
        if (maxMem[j] != 0) {
            //현재 보는 애의 정보를 더 해주기만 한다 와우
            maxMem[j + cost[i]] = max(maxMem[j] + mem[i], maxMem[j + cost[i]]);
        }
    }
}

이렇게 하면 되더라
흐음 배열에 값이 있는 부분만 내가 예전에 처리한 부분이구나! 를 느꼈다

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

int n, m, maxCost;

int mem[105], cost[105];
int maxMem[10005];
//index 비용으로 최대 value 바이트 수를 확보할 수 있다
//cost가 0에서 100 사이 값이니까 값이 다 100일 때 n이 100이면 최대 될 수 있는 cost합은 10000

/*
	5 60
	35 40 30 10 20
	5 4 3 0 3 일때

	costmem[5]=35

	costmem[9]=75
	costmem[4]= 40

	costmem[8]=65
	costmem[12]=105
	costmem[7]= 70
	costmem[3]=30
*/

int findMaxMem() {
	//전체 돌면서 만들 수 있는 조합 만들기
	for (int i = 0; i < n; i++) {
		//그동안 돈 애들로 만들 수 있는 최대 바이트 수 저장해놓고 그 안에만 돌자!
		maxCost += cost[i];

		//기존에 만든 조합에 i번째 애가 들어가서 더 최대 값을 만들 수 있냐?
		for (int j = maxCost; j > 0; j--) {
			if (maxMem[j] != 0) {
				//0이 아니면 예전에 이 값일 때 어떤지 봤었음
				maxMem[j + cost[i]] = max(maxMem[j] + mem[i], maxMem[j + cost[i]]);
			}
		}

		//i번째 애만 있는 경우에 더 최대 값을 만들 수 있냐?
		maxMem[cost[i]] = max(mem[i], maxMem[cost[i]]);
	}

	//cost가 작을 때 부터 확인하면서 원하는 크기 이상 메모리를 만들 수 있으면 반환
	for (int i = 0; i <= maxCost; i++) {
		if (maxMem[i] >= m) {
			return i;
		}
	}

	return 0;
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> mem[i];
	}

	for (int i = 0; i < n; i++) {
		cin >> cost[i];
	}

	cout << findMaxMem();

	return 0;
}