[JAVA]백준 17521번: Byte Coin

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

17521번: Byte Coin

1. 문제 설명

 

문제

• 1일부터 n일까지 n일동 안 바이트 코인의 등락을 미리 알 수 있으며 우리에게는 초기 현금 W가 주어져 있다.
• 매일 바이트 코인을 매수하거나 매도할 수 있다.
• 바이트 코인 하나를 나누어 매도하거나 매수할 수 없다.
• 우리는 n일날 보유하고 있는 모든 코인을 매도할 때 가지고 있는 현금을 최대화하고 싶다.
• 요일 수 n, 초기 현금 W, 1일부터 n일까지 각 요일의 바이트 코인 가격이 주어질 때, n 일어날 보유하고 있는 모든 코인을 매도할 때 보유하게 될 최종 현금의 최댓값을 출력

조건

• 1<=n<=15
• 1 <=W <=100,000
• 1 <=코인 가격 <=50

 

2. 풀이

 

코인은 언제 사서 언제 파는 게 이득일까?

 

쌀 때 사서 비쌀 때 파는 것이다.

 

그리고 이것을 많이 반복하면 할수록 돈을 불려 나갈 수 있다.

 

이것은 바탕으로 생각해보면 2가지 로직이 나온다.

 

이전에 코인을 구매한 적이 없고, 현재 가격이 다음 가격보다 낮은 경우 구매한다.

현재 가격이 다음 가격보다 높은 경우 판매한다.

 

이를 바탕으로 n일날까지 구해가면 답을 구할 수 있다.

 

주의할 점은 int 형이 아닌 long형으로 선언해야 한다는 것이다.

 

가능한 최대 값은 1,50이 15일까지 반복되며, 초기 값이 1000원일 때 1000*50^7이다.

int의 범위를 벗어나므로 long형으로 선언해 주어야 한다.

 

3. 코드

// JAVA 11 , 메모리 : 14232KB, 시간 : 128ms

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int days;
        long money, coin = 0;
        int min = 51, max = 0;
        int now = 0;
        int[] price;

        StringTokenizer st = new StringTokenizer(br.readLine());

        days = Integer.parseInt(st.nextToken());
        money = Long.parseLong(st.nextToken());

        price = new int[days];

        for (int x = 0; x < days; x++) {
            price[x] = Integer.parseInt(br.readLine());
        }

        for (int x = 0; x < days-1; x++) {
            // 이전에 구매한 적 없고, 현재 가격이 다음 가격보다 낮은 경우 -> 구매
            if (coin == 0 && price[x] < price[x + 1]) {
                coin = money / price[x];
                money -= coin * price[x];
            }

            //현재 가격이 다음 가격보다 높을 때 -> 판매
            if (price[x] > price[x + 1]) {
                money += coin * price[x];
                coin = 0;
            }
        }

        // 마지막날은 가지고 있는 코인을 전부 판매한다.
        money += coin * price[days-1];


        System.out.println(money);

    }


}