[ICPC] What’s Mine is Mine

백준 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으로 하는 광물을 모두 넣었다

이렇게 풀었더니 맞는 결과가 나오게 되었다

 

#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]);
}

 

이때 DP 배열은 end time의 최대값까지 채워주었고, 벡터에 보석의 값을 체크할 때는 미리 ( end time - start time ) * price를 해서 채워넣었다