[C++] Gazzzua (백준 17939번)

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

 

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

int n;
vector<int> c;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    c = vector<int>(n);
    for (int i = 0; i < n; i++) cin >> c[i];

    int ans = 0;
    int s = 0;
    int e = c.size();
    while (s < e) {
        int maxv = 0;
        int maxi = -1;
        for (int i = s; i < e; i++) {
            if (c[i] >= maxv) {
                maxv = c[i];
                maxi = i;
            }
        }
        for (int i = s; i < maxi; i++) {
            ans -= c[i];
        }
        ans += maxv * (maxi - s);
        s = maxi + 1;
    }

    cout << ans << '\n';
}

일단 처음에는 전체 구간에서 최댓값을 찾고, 최대 전까지 계속 사다가 최대인 지점에서 다 팔았다. 그리고 구간을 최대 지점을 기준으로 잘라 뒷부분으로 줄이고 다시 반복하고... 구간의 길이가 1이 될 때까지 반복했다. 그리디 알고리즘 문제였다. (정답)

 

---

 

오랜만에 랜디했다. 실2~골5로 했다. 랜디 딱 돌리고 보니까 제목이 영어라서 윽 영어문제?! 넘길까?? 했는데 문제만 영어였다. 문제 풀고 제목을 다시 읽어보기 가주아 ㅋㅋㅋ 요즘 엘리스 푸느라 하루의 PS 에너지를 다 써서 백준 스트릭은 항상 쉬운걸로 풀었다. 따라서 매우 오랜만에 쓰는 글.. 엘리스 복기 글도 써야겠다.