코드 복사/붙여넣기 하는 당신이 아름답습니다.

15748 : Rest Stops

풀이

그리디하게 풀면 된다.

가장 큰 값까지 간 다음 가능한 시간 동안 계속 풀을 뜯어 먹는다.

그리고 이후의 값들 중 가장 큰 값을 찾고

이 동작을 반복한다.

코드

#include <cstdio>
#include <algorithm>
long long l, n, r, f, b, x[100003], c[100003];
int main() {
    scanf("%lld %lld %lld %lld", &l, &n, &f, &b);
    for (int i = 1; i <= n; i++) scanf("%lld %lld", &x[i], &c[i]);
    for (int i = n; i >= 1; i--)
        r += (f - b) * (x[i] - x[i-1]) * (c[i] = std::max(c[i], c[i+1]));
    printf("%lld\n", r);
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-17 12:26

Read more posts by this author