Boj 31964 c++ 반품회수

풀이시간 약 40분

풀 수 있을 것 같았는데 5점을 연속으로 맞으면서 정신이 혼미해졌다. 하지만 정신을 다잡고 방법을 바꾸어 정답을 맞추었다.

다행히도 구글링 찬스는 사용하지 않았다. 아마도 그리디의 해법은 항상 내가 맞을 것이라고 믿지 않고 계속해서 다른 방법을 시도해보는 것 밖에 없을 듯 하다. 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


int dp[3001];//두 지점 사이의 거리
int main(){

    int N;
    long long tot=0;

    cin>>N;

    vector<pair<int, int>> v(N);

    for(int i=0; i<N; i++){
        cin>>v[i].first;//거리
    }
    for(int i=0; i<N; i++){
        cin>>v[i].second;//택배시간
    }
    sort(v.begin(), v.end());//택배거리 순으로 정렬
    reverse(v.begin(), v.end());

    dp[0]=v[0].first;

    for(int i=1; i<N; i++){
        int dist=v[i].first-v[i-1].first;
        dp[i]=((dist>0) ? dist : dist*-1);
    }

    for(int i=0; i<N; i++){
       int current=v[i].first;
       long long delay=v[i].second;
       tot+=dp[i];//거리 더해주기
       if(delay>tot){
        tot=delay;
       }
    }
    tot+=v[N-1].first;
    cout<<tot;

}

 

회의가 시작하는 시간을 기준으로 정렬을 했던 1931과는 달리, 31964는 거리순 정렬이 최적해를 구하는 방법이였다. 정확한 해법인지는 모르겠지만 아마도 가장 멀리 있는 지점 부터 방문하는 것이 가장 시간 상으로 값싼 선택이었으리라 추측해본다.

 

그리디 문제는 앞으로 더 많이 풀어야 할 듯 싶다.