백준 17979번으로 풀어본 icpc 지역 예선 문제 마지막 번호였던 L번
역시 문제 순서랑 난이도는 다르다
이 문제는 여러 종류의 광석이 있고 그 광석들을 채굴할 때 가장 돈을 많이 벌 수 있는 경우를 찾는 문제이다
이 때 광석을 캐서 벌 수 있는 돈은 광석이 나오는 (end time - start time) * price이다
DP로 풀면 될 것 같아서 먼저 DP 식을 세워보았다
DP[i] = i시간까지 채굴해서 얻을 수 있는 최대 금액
그리고 여기에 이전 값을 어떻게 활용할지에 대해 생각해보았다
현재 시간이 특정 광물의 end time일 때 그 광물의 start time의 DP값에서 이 광물을 더 한 것이 DP[i-1]보다 큰 지 확인해보았다
이 부분에서 실수를 해서 처음 풀이가 틀렸는데 특정 시간에 광물의 end time이 하나 일 것이라고 생각한 점이 문제였다
end time이 하나일 것이라고 생각해서 map의 key를 end time으로 하고 value를 start time과 가치의 pair로 작성하였는데 예제는 잘 돌아갔지만 채점 결과 틀렸습니다라는 문구를 볼 수 있었다
다시 문제를 살펴 보니 end time이 여러개가 있을 수 있겠다고 판단하여 vector 배열을 사용하였다
vector 배열의 index가 end time이 되고 vector에 해당 index를 end time으로 하는 광물을 모두 넣었다
이렇게 풀었더니 맞는 결과가 나오게 되었다
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
|
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int minerals[101];
int DP[15005];
vector<pair<int, int> > vec[10005]; //vec[i] : end time, pair<int,int> : start, val
int main(){
int m,n;
scanf("%d%d",&m,&n);
for(int i = 1 ; i <= m ; i++) scanf("%d",&minerals[i]);
int limit = 0;
while(n--){
int s,e,t;
scanf("%d%d%d",&s,&e,&t);
if(limit<e) limit = e;
vec[e].push_back(make_pair(s,(e-s)*minerals[t]));
}
for(int i = 1; i <= limit; i++){
DP[i] = DP[i-1];
for(auto it = vec[i].begin() ; it != vec[i].end() ; it++){
if(DP[i]<DP[it->first]+it->second) DP[i] = DP[it->first]+it->second;
}
}
printf("%d\n",DP[limit]);
}
|
cs |
이때 DP 배열은 end time의 최대값까지 채워주었고, 벡터에 보석의 값을 체크할 때는 미리 ( end time - start time ) * price를 해서 채워넣었다
'알고리즘' 카테고리의 다른 글
[ICPC] Parentheses (0) | 2020.09.24 |
---|---|
[ICPC] Working Plan (0) | 2020.09.22 |
[ICPC] Fire on Field (0) | 2020.09.13 |
[C++] 백준 5052번 : 전화번호 목록 (0) | 2020.06.13 |
[C] 백준 3978번 : Hacking (0) | 2020.06.13 |