[백준 17521번] Byte Coin

문제 링크: https://www.acmicpc.net/problem/17521

17521번: Byte Coin

<문제 풀이> 그리디 알고리즘

 

다음 날에 가격이 증가하면 코인을 모두 매수하고, 감소하면 코인을 모두 매도하면 됩니다.

 

<C++소스코드>

#include<iostream>
using namespace std;
 
typedef long long ll;
ll n, w;
ll price[16];
void input() {
    cin >> n >> w;
    for (int i = 1; i <= n; i++) cin >> price[i];
}
 
void solve() {
    input();
    ll cur = price[1];
    ll coin = 0;
    for (int i = 2; i <= n; i++) {
        int next = price[i];
        if (next > cur) { // 다음 날에 가격이 증가하면
            coin += w / cur; // 최대한 코인을 매수한다.
            w %= cur;
        }
        else if (next < cur) { // 감소하면
            w += coin * cur;// 코인을 모두 매도한다.
            coin = 0;
        }
        cur = next;
    }
    w += coin * cur; // 마지막 날 코인을 모두 매도한다.
    cout << w;
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}