[백준,c++] 17521번 - Byte Coin

문제

17521번: Byte Coin

 

코드

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll n, w; cin>>n>>w;
    ll coin = 0;
    vector<int>v(n+1);
    for(int i=0; i<n; i++) cin>>v[i];
    
    for(int i=0; i<n; i++){
        if(v[i]<v[i+1]){    // 코인 구매
            coin += w/v[i];
            w = w%v[i];
        }
        else{   // 코인 판매
            w += v[i]*coin;
            coin = 0;
        }
    }
    cout<<w;

}

 

풀이

DP문제인가.. 고민했지만 단순히 배열의 인덱스만 비교해주면 손쉽게 풀리는 그리디 문제였습니다.

• 오늘보다 내일이 더 비싸면 오늘 코인을 구매한다.
• 오늘보다 내일이 더 싸면 오늘 코인을 전부 판매한다.