[ICPC] 백준 17521 - Byte Coin

www.acmicpc.net/problem/17521

 

자본금으로 얼마나 많은 수익을 얻을 수 있을지 구하는 문제이다.

 

바이트 코인 예측 금액을 나열한 차트를 단조 감소하는 구간과 단조 증가 하는 구간으로 분리하여 단조 감소를 만족하는 마지막 날에 풀매수하고 단조 증가를 만족하는 마지막 날에 풀매도하면 최대 이익을 얻을 수 있다.

 

단조 감소 구간을 추적하는 L 포인터와 단조 증가 구간을 추적하는 R 포인터를 통해 최적 매수/매도 날짜를 탐색한 후 이를 계산하는 방식으로 구현했다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main()
{
    int days;
    ll seed;
    cin >> days >> seed;

    if (days == 1)
    {
        cout << seed;
        return 0;
    }

    int l = 0, r = 1;

    vector<int> chart(days);

    for (int i = 0; i < days; ++i)
        cin >> chart[i];
    
    ll cnt = 0;
    
    while (l < days && r < days)
    {
        if (chart[l] < chart[r])
        {
            if (r == days - 1 || (r < days - 1 && chart[r] > chart[r + 1]))
            {
                cnt = seed / chart[l];
                seed -= cnt * chart[l];
                seed += cnt * chart[r];
                cnt = 0;
                int pivot = r;
                l = pivot + 1, r = pivot + 2;
            }
            else
            {
                ++r;
                continue;
            }
        }
        else
        {
            int pivot = r;
            l = pivot, r = pivot + 1;
        }
    }

    cout << seed;
}