관리 메뉴

Joonas' Note

BOJ 17521 - Byte Coin 본문

알고리즘/문제 풀이

BOJ 17521 - Byte Coin

joonas 2019. 11. 6. 20:35

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

    문제

    보자마자 주식 문제가 생각났다.

    주식 문제들은 최대 이익을 내기 위해서 그리디하게 행동하면 된다. 값쌀 때 사서 값비쌀 때 팔면 된다.

    이 문제에서는 늘어난 코인만큼 다시 투자를 할 수 있으니, 상승 곡선이면 무조건 사는것이 이득이다. (늘어난 코인을 배로 불릴 수 있으니)

    코드


    직관적으로 풀었지만 내심 불안했다.

    그래서 dp로도 풀어보았다. 물론, 같은 결과가 나왔고 정답이다.

    점화식은 dp[k] := k일까지 벌 수 있는 최대 코인이다.

    \(i < j\) 인 \(i\)일째에 가진 돈으로 전부 매수하고, \(j\)일에 모두 매도한다면 (두 날짜 사이의 변폭) * (i일에 살 수 있었던 코인의 수)만큼 벌 수 있을것이다.


    반응형

    '알고리즘 > 문제 풀이' 카테고리의 다른 글

    BOJ 17520 - Balanced String  (0) 2019.11.07
    BOJ 1699 - 제곱수의 합  (0) 2019.11.06
    BOJ 5612 - 터널의 입구와 출구  (0) 2019.11.06
    BOJ 13325 - 이진 트리  (0) 2019.09.16
    UVa 10918 - Tri Tiling  (3) 2019.04.15
    0 Comments
    댓글쓰기 폼