글 읽기 - 1446 지름길 문제 greedy로 풀면안되나요??

nisroeld99 8년 전 0

1순위 . 단축이 가장많이 되는 경로

2 순위 . 끝점이 빠를 수록

3순위 시작점이 느릴수록

이런 기준으로 경로들 다 넣고 greedy돌려도 답이 안나오네요...

어디가 틀린걸까요

///

그러면 이문제는 dp로 푸는건가요? ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

vector<iii> v;
vector<iii> dab;

int cmp (const iii & v1, const iii & v2 ){
    if ((v1.second.first-v1.second.second)+v1.first  == ((v2.second.first-v2.second.second)+v2.first ) ) { //지름길 축소가 같다면
        
        if ( v1.second.first == v2.second.first  ) { //도착지가같다면
          
            return v1.second.second > v2.second.second;  //출발지가 느릴 수록
        }
        
        return  v1.second.first < v2.second.first;  //도착지가 빠를수록
    }

 
    
    
    return  ((v1.second.first-v1.second.second)+v1.first ) > ((v2.second.first-v2.second.second)+v2.first );

}

int main(){
    int n, d ;
    
    cin>>n>>d;
    
    while ( n-- ) {
        int sc1,sc2,sc3;
        scanf("%d%d%d", &sc1,&sc2,&sc3);
        if (sc2>d ) continue;          // 도착지가 지나가면 continue;
        if ( sc2-sc1 < sc3) continue ; //소용없으면 continue;

        v.push_back(iii(sc3, ii  (sc2,sc1 )  ) ); // 지름길 1순위 , 도착지 2순위 출발지 3순위
    }
    
    sort ( v.begin() , v.end() , cmp);  // 위에서 말한 순위 기준으로 정렬
   
    int start = v[0].second.second;
    int end = v[0].second.first;
    
    dab.push_back(iii (v[0].first  , ii(end,start) )   );
    
    for (int i = 1  ;  i < v.size() ; i++){
        if ( v[i].second.second >= end ){
            start = v[i].second.second;
            end= v[i].second.first;
            dab.push_back(iii (v[i].first  , ii(end,start) )   );
        }
    }
   for (int i =0 ; i < dab.size() ;i++){
        cout<<dab[i].second.second << ' ' <<dab[i].second.first <<' ' << dab[i].first<<endl;
    }
    
    
    int ans = d;
    for (int i = 0 ; i < dab.size() ; i++){
        ans-= (dab[i].second.first - dab[i].second.second );
        ans += dab[i].first;
             
    }
    
    cout << ans<<endl;
                  
    
    

}

yclock 8년 전 1

~~문제를 풀어보지도 않았고, 소스를 자세히 읽지도 않았습니다. (죄송합니다.)~~

2 10000

0 10000 9999

1 9999 1

이런 경우가 있으면 그리디로는 힘들지 않을까요....?

nisroeld99 8년 전 0

ㄱㅡ럼 어떤 알고리즘을 써야하나요 ㅠㅠ

yclock 8년 전 0

~~문제 스포일려나..?~~

정렬 한 번만하고, dp를 처음부터 쓱하고 돌면 될 듯 싶습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1446 지름길 문제 greedy로 풀면안되나요??

nisroeld99 8년 전 0

yclock 8년 전 1

nisroeld99 8년 전 0

yclock 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말