티스토리 뷰

PS/백준

[백준/C++] 15748번 - Rest Stops

unside 2021. 3. 12. 14:59

오늘의 문제!

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

입력

첫줄에 L N rF rB 가 순서대로 주어지고 이어서 N개의 줄에 xi Ci가 주어진다

풀이

Ci의 값이 가장 큰 위치에서 쉬는게 가장 이득이다 가장 큰 곳에서 쉬고 그다음으로 가장 큰 곳에서 쉬는 식으로 하는게 가장 높은 값을 얻을 수 있다. 예를 들어
10 5 4 3
1 3
3 7
4 5
6 6
7 3
이라고 하면 선택할 쉼터는 (3,7) (6,6) (7,3) 이 되는 식이다

소스

Ci의 값이 최대인 경우만 바라보면 되기 때문에 힙을 사용했다. 현재위치는 curPoi 변수를 사용해서 확인해줬으며 xi의 값이 curPoi보다 작은경우는 넘어가 줬다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
struct data {
    int x;
    int c;
};
 
struct cmp {
    bool operator()(data a, data b){
        return a.c < b.c;
    }
};
 
priority_queue<data,vector<data>,cmp> inpArr;
 
int main(void){
    long long L, N, rF, rB;
    cin >> L >> N >> rF >> rB;
    for(int i=0;i<N;i++){
        int x,c;
        cin >> x >> c;
        inpArr.push({x,c});
    }
    int curPoi = 0;
    long long sum = 0;
    while(!inpArr.empty()){
        data a = inpArr.top();
        if(curPoi < a.x){ //쉴 수 있는 쉼터
            sum = sum + ((a.x-curPoi)*rF - (a.x-curPoi)*rB)*a.c;
            curPoi = a.x;
        }
        inpArr.pop();
    }
    cout << sum;
    return 0;
}
 
cs
저작자표시 비영리 동일조건

'PS > 백준' 카테고리의 다른 글

[백준/C++] 1629번 - 곱셈  (0) 2021.03.18
[백준/C++] 1493번 - 박스 채우기  (0) 2021.03.17
[백준/C++]13904번 - 과제  (0) 2021.03.11
10989번 수 정렬하기 3  (0) 2019.06.27
2750번 수 정렬하기  (0) 2019.06.27
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/02   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함