[C언어] 백준 17521번: Byte Coin

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

17521번: Byte Coin

 

1일	매수	코인 4개	현금 24 - 20 = 4
2일	매도	코인 0개	현금 4 + 28 = 32
3일	매도	코인 0개
4일	매도	코인 0개
5일	매수	코인 16개	현금 32 - 32 = 0
6일	매수		현금 = 0
7일	매도	코인 0개	현금 0 + 128 = 128
8일	매도	코인 0개
9일	매수	코인 42개	현금 128 - 126 = 2
10일	매도	코인 0개	현금 2 + 168 = 170 (최대)

 

 - 극댓값이 아닌 곳에서 매도하려고 하면, 코인이 없다.

 - 극솟값이 아닌 곳에서 매수하려고 하면, 현금이 없다.

 - 따라서 그냥 오늘이 다음날보다 비쌀 때 매도하고, 오늘이 다음날보다 쌀 때 매수하도록 코드를 짠다.

 

#include <stdio.h>
int main(){
    int n, *price;
    long long money, coin = 0;

    scanf("%d %lld", &n, &money);
    price = malloc(sizeof(int)*n);
    for (int i = 0; i < n; i++) scanf("%d", &price[i]);

    for (int i = 0; i < n; i++){
        //오늘이 다음날보다 비쌀 때, 매도  
        if (price[i] > price[i+1]){
            money += coin * price[i];
            coin = 0;
        }
        //오늘이 다음날보다 쌀 때, 매수  
        if (price[i] < price[i+1]){
            long long temp = money / price[i];	//살 수 있는 코인의 개수 
            money -= temp * price[i];
            coin += temp;
        }
    }
    //마지막 날(n일), 모두 매도 
    money += coin * price[n-1];
    printf("%lld", money);
    return 0;
}