#문제
https://www.acmicpc.net/problem/7579
#작성 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
#include <vector>
using namespace std;
int n, M;
vector<int> mem;
vector<int> cost;
int d[10001];
// d[cost]에 cost를 만족하는 최대로 확보 가능한 메모리 크기를 저장한다.
int main(){
// 입 력
cin>>n>>M;
for(int i=0; i<n; i++){
int m;
cin>>m;
mem.push_back(m);
}
for(int i=0; i<n; i++){
int c;
cin>>c;
cost.push_back(c);
}
// d배열 값을 모두 -1로 초기화
fill_n(d, 10001, -1);
// 필요한 메모리 M바이트를 확보하기 위한 앱 비활성화의 최소비용 계산.
for(int i=0; i<n; i++){
int c = cost[i];
for(int j=10000; j>=c; j--){
if( d[j-c]==-1 ) continue; // 계산된적있는 j-c에 대해서만 계산
d[j] = max(d[j], d[j-c]+mem[i]);
// i번째 app을 포함하는 경우와 포함하지 않는 경우 중 확보 메모리가 더 큰 경우 저장.
}
if( d[c]<mem[i] ) d[c] = mem[i];
}
for(int i=0; i<10001; i++){
if( d[i] >= M ){
// 작은 cost부터 탐색, 최초로 확보 메모리가 M 이상인 경우 cost 출력
cout<<i<<'\n';
return 0;
}
}
}
|
cs |
##
메모리 확보를 위한 앱 비활성화는 1회만 가능하기 때문에(4781번 사탕가게 문제처럼 한 종류의 사탕을 여러번 사는 것이 불가능.)
for(int j=10000; j>=c; j--){} 와 같이 cost를 역순으로 줄여나가며 메모이제이션을 수행한다.
'BOJ' 카테고리의 다른 글
| BOJ 2261번 :: 가장 가까운 두 점 (0) | 2020.01.27 |
|---|---|
| BOJ 4781번 :: 사탕가게 (0) | 2020.01.23 |
| BOJ 1520번 :: 내리막 길 (0) | 2020.01.09 |
| BOJ 12015번 :: 가장 긴 증가하는 부분 수열 2 (0) | 2020.01.06 |
| BOJ 11055번 :: 가장 큰 증가 부분 수열 (0) | 2020.01.06 |