[BOJ 17521] Byte Coin (ICPC 2019)

문제 출처 : https://www.acmicpc.net/problem/17521

 

풀이 :

 

2019 ICPC 예선문제입니다.

모든 정보를 알기 때문에

최대의 이익을 뽑아내기 위해서는 항상 저점 매입해서 고점에서 매도하면 됩니다.

 

#include<stdio.h>
int n, arr[16], ma, mi;
long long int k;
int main()
{
    scanf("%d %lld", &n, &k);
    for (int i = 0; i < n; i++)scanf("%d", &arr[i]);
    mi = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (mi < arr[i])
        {
            ma = arr[i];
            ++i;
            for (i; ma < arr[i] && i < n; i++)ma = arr[i];
            k = (k / mi)*ma + k % mi;
        }
        mi = arr[i];
    }
    printf("%lld", k);
}