[C++] 백준 15748번: Rest Stops

🔗 문제

https://www.acmicpc.net/problem/15748

15748번: Rest Stops

 

🖍 풀이

 

* 이 문제 전에 boj 회의실 배정, 강의실 배정을 순서대로 푸는 걸 권장한다. 

 

 

당연히 가치가 큰 휴식처에서 쉬는게 좋다는 것 까지는 눈치 챘을 것이다.

비교 함수를 커스텀해서 정렬 순위를 1. 가치 내림차순 2. 위치 오름차순으로 정렬해준다. 

struct compare
{
    bool operator()(const pll& a, const pll& b)
    {
        if(a.second == b.second)
            return a.first < b.first;

        return a.second > b.second;
    }
};

 

 

그렇다면 식을 세우면서 어려움을 겪었을 것 같다. 

나는 식이 너저분해서 검색을 통해 소스 정리 좀 했다. 

B가 이동한 거리 / (Rf-Rb)가 F가 따라오는데 걸리는 시간이다.

그 시간만큼은 B가 쉬어도 F보다 뒤쳐질 수가 없다.

 

ll pos = 0LL; // 현재 위치 
for(ll i=0; i<N; ++i)
{
	  x = p[i].first; // 휴식처 위치
	  c = pq[i].second; // 휴식처 가치
	  
	  // 휴식처가 이미 지나간 경로에 있으면 무시
	  if(pos >= x) 
	      continue;

	  // 휴식처가 앞에 있다면 가치를 추가해준다. 
	  sum += (x - pos)*(F-B)*c;
	  pos = x;
}

우선순위 큐로 풀어도 되지만 for문안에서 원소 변동이 없어서 굳이 안 썼다.

 

💾  소스

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

typedef long long ll;
typedef std::pair<ll, ll> pll;

struct compare
{
    bool operator()(const pll& a, const pll& b)
    {
        if(a.second == b.second)
            return a.first < b.first;

        return a.second > b.second;
    }
};

int main()
{
    std::vector<pll> p;
    
    ll x, c, sum = 0;
    ll L, N, F, B;
    std::cin >> L >> N >> F >> B;
    for(ll i=0; i<N; ++i)
    {
        std::cin >> x >> c;
        p.push_back({x, c});
    }
    
    std::sort(p.begin(), p.end(), compare());
  
    ll pos = 0LL;
    for(ll i=0; i<N; ++i)
    {
        x = p[i].first;
        c = p[i].second;

        if(pos >= x)
            continue;
        
        sum += (x - pos) * (F-B) *c;
        pos = p[i].first;
    }
    std::cout << sum;
    
    
    return 0;
}