백준[13305] 주유소

어려운 문제...ㅠ

 

문제를 풀때 생각한 경우의 수

1. 현재 도시 주유소에서 현재 주유소 보다 저렴하고 가까운 다른 도시 주유소 까지 거리 x 현재 주유소 가격
2. 현재 주유소가 가장 저렴한 경우

위 경우의 수를 생각하고 문제를 풀었는데...

문제 3번의 조건이 충복이 되지 않는다고 한다 ㅠ

 

□ 소스 코드

#include <bits/stdc++.h>

/*
 가격이 가장 싼 주유소가 나오면 남은 거리 모두 주유
 도시에서 자신보다 작은 가격이 있는 경우 해당 지점거리 까지만 주유, 없는 경우 끝까지 주유
 */
void gasStation(){
    int n;  //도시 개수
    cin>> n;
    
    vector<int> km;
    vector<int> price;
    int totaldis = 0;
    // 각 도시 사이의 거리 입력
    for(int i=0;i<n-1;i++){
        int dis;
        cin>> dis;
        totaldis += dis;
        km.push_back(dis);
    }
    
    // 각 도시 주유소의 기름 가격
    for(int i=0;i<n;i++){
        int pr;
        cin>>pr;
        price.push_back(pr);
    }
    
    int result = 0;
    
    // 각 도시를 이동하는 것
    for(int i=0;i<n-1;i++){
        bool checkMinPrice = false; //가격이 가장 작은 주유소 찾는 변수
        bool finishLoop = false;    //다른 도시들을 검색했을 때 현재 주유소가 가장 싼 주유소 인경우
        int disIndex = 0;   //가장 싼 주유소 인덱스
        
        // 현재 도시 말고 다른 도시 탐색
        for(int j=i+1;j<n;j++){
            if(price[i] > price[j] && checkMinPrice == false){  // 현재 가격 보다 가격이 저렴한 주유소 판별
                disIndex = j;       //인덱스 저장
                checkMinPrice = true;
            }
            // 모든 도시들을 다 검사해도 i도시가 제일 싼 경우
            if( checkMinPrice == false && j == n-1){
                int leftDis = 0;
                for(int k = i;k<n;k++){ // 도착점까지 남은 거리 계산
                    leftDis += km[k];
                }
                result += price[i] * leftDis;
                finishLoop = true;
                break;
            }
        }
        if(finishLoop){ 
            break;
        }
        // i 도시 주유 가격보다 싼 도시 까지 거리만큼 주유하는 비용
        if(checkMinPrice){
            int sumKm = 0;
            for(int j=i;j<disIndex;j++){    // 주유가격보다 싼 도시까지 거리 합산
                sumKm += km[j];
            }
            result += price[i] * sumKm;     //현재 가격 * 거리
            i = disIndex-1;
            checkMinPrice = false;
        }
        
    }
    
    cout<<result<<endl;
    
}

어떤 경우의 수가 더 존재하는지 모르겠다...

 

다음에 수정해야지

58점

 

---

23년 1월 6일 

100점 성공!

 

생각을 잘못하여 문제에 접근을 잘못 했다.

모든 주유소를 가지만 현재 주유소 가격이 전 주유소 가격보다 저렴한 경우 전 주유소 가격으로 기름값을 계산하면 된다.

이 생각을 하기가 그렇게 힘들다니..ㅠ

 

□ 성공한 소스코드

#include <bits/stdc++.h>

/*
매 도시를 진입한다고 생각하고 각 거리에 이전에 가장 저렴한 가격의 기름값을 곱한다.
*/

void gasStation(){
    int n;  //도시 개수
    cin>> n;
    
    vector<unsigned long long> km;
    vector<unsigned long long> price;
    unsigned long long totaldis = 0;
    
    // 각 도시 사이의 거리 입력
    for(int i=0;i<n-1;i++){
        long long dis;
        cin>> dis;
        totaldis += dis;
        km.push_back(dis);
    }
    
    // 각 도시 주유소의 기름 가격
    for(int i=0;i<n;i++){
        long long pr;
        cin>>pr;
        price.push_back(pr);
    }
    
    unsigned long long result = 0;
    long long minOilPrice = price[0];
    
    for(int i=0 ;i<n-1;i++){
        // 가격이 지금보다 저렴한 기름 값 저장
        if(minOilPrice >= price[i]){
            minOilPrice = price[i];
        }
        result += km[i] * minOilPrice;   
    }
    cout<<result<<endl;    
}

생각을 바꿔서 다시 푸니까 간단한 문제였다..