BOJ 17521 - Byte Coin

문제

백준 온라인 저지 - 17521번

풀이 과정

바이트 코인 의 시세가 주어질 때 매수 및 매도를 통해 얻을 수 있는 최대 이익을 계산하는 문제입니다.

매수 및 매도 횟수에 제한이 없기 때문에 그래프의 극대 및 극소 지점에서 매도 및 매수를 진행하는 그리디 해법이 적용됩니다.
각각의 순회에서 이전 가격과 비교하여 그래프의 상승 및 하강을 파악할 수 있으며
마지막에 매도하지 않고 남은 코인이 존재할 경우 이전에 극소 지점에서 코인을 구매하고 아직 판매하지 못한 것이기 때문에
극대 지점을 갱신 중인 상황이라는 것을 의미하고 따라서 마지막 날의 시세에 팔면 최대 이익을 취할 수 있습니다.

코드

import sys

N, W = list(map(int, sys.stdin.readline().split()))
coins = [int(sys.stdin.readline()) for _ in range(N)]


def solution(budget):
    coin_count, prev = 0, coins[0]

    for price in coins[1:]:
        if prev > price and coin_count:
            # 매도
            budget += coin_count * prev
            coin_count = 0
        elif prev < price and not coin_count:
            # 매수
            coin_count = budget // prev
            budget -= coin_count * prev

        prev = price

    # 현재 매도하지 않은 코인이 있다는 것은 이전에 최저가에 구매한 이력이 있다는 의미
    if coin_count:
        budget += coin_count * coins[-1]

    return budget


print(solution(W))