백준 17521) Byte Coin [kotlin, java]

문제

국제자본부동산회사(ICPC)는 바이트 코인(Byte Coin)에 자금을 투자하고 있다. 바이트 코인은 김박사가 만든 가상 화폐이다. 실제로는 바이트 코인 가격을 예상할 수 없지만 이 문제에서는 바이트 코인 가격 등락을 미리 정확히 예측할 수 있다고 가정하자.

우리는 1일부터 n일까지 n일 동안 그림 1과 같이 바이트 코인의 등락을 미리 알 수 있으며 우리에게는 초기 현금 W가 주어져 있다. 그림 1의 빨간색 네모는 해당 일자의 바이트 코인 가격을 나타낸다. 매일 바이트 코인을 매수하거나 매도할 수 있다고 하자. 다만 바이트 코인 하나를 나누어 매도하거나 매수할 수는 없다. 우리는 n일 날 보유하고 있는 모든 코인을 매도할 때 가지고 있는 현금을 최대화하고 싶다. 

 

 

그림 1. 10 일간 바이트 코인 가격 등락 그래프

예를 들어, 그림 1과 같은 바이트 코인 등락 그래프를 첫날 미리 알 수 있다고 하고 우리에게 주어진 초기 현금이 24라고 하자. 수익을 최대한 높이려면 다음과 같이 바이트 코인을 매수, 매도할 수 있다. 첫 날 현금 20을 써서 4개의 코인을 산다. 둘째 날 모든 코인을 매도해서 현금 28을 얻고 모두 32의 현금을 갖게 된다. 5일째 되는 날 현금 32를 써서 16개의 코인을 매수한다. 7일째 되는 날 모든 코인을 매도해서 모두 128의 현금을 갖게 된다. 9일째 되는 날 현금 126을 써서 42개의 코인을 사고 10일 날 모든 코인을 매도한다. 그러면 10일 날 현금이 170이 되고 이것이 최대이다.

요일 수 n, 초기 현금 W, 1일부터 n일까지 각 요일의 바이트 코인 가격이 주어질 때, n일 날 보유하고 있는 모든 코인을 매도할 때 보유하게 될 최종 현금의 최댓값을 출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 요일 수를 나타내는 양의 정수 n과 초기 현금 W(1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000)가 주어진다. 다음 n 개의 줄에서, i번째 줄은 i일의 바이트 코인 가격을 나타내는 정수 si가 주어진다(1 ≤ si ≤ 50).

출력

출력은 표준출력을 사용한다. n일 날 보유하고 있는 모든 코인을 매도할 때 가지고 있는 현금의 최댓값을 한 행에 출력한다. 비록 초기 현금 W는 그렇게 크지 않지만 최종 현금은 매우 커질 수 있음에 주의하자.

 

---

 

이 문제의 요약은 다음과 같다.

• 최소가 될 때 매수를 하고, 최대가 될 때 매도를 한다.
• 단, 마지막 날은 매도를 한다.

 

나는 해당 문제를 풀면서 다음과 같은 로직을 떠올렸다.

 

 

1. 최소가 되는 지점, 최대가 되는 지점을 컬렉션에 저장한다.

 

 

arr[i] : 현재 배열, arr[i+1] : 다음 배열일 때,

 

2. arr[i] < arr[i+1]이라면 arr[i]가 최소가 된다. 단, min 변수에 최솟값을 넣고 다음 배열 arr[i+1]와 arr[i+2] 중에서 arr[i+1]가 작아도 arr[i]가 최소임을 보장하게 한다.

 

 

3. 이후에는 최댓값을 구하는 차례이므로 max 변수를 0(바이트 코인 가격이 최소 1) 으로 초기화한다.

 

 

4. arr[i] > arr[i+1]이라면 arr[i]는 최대가 된다. 단, max 변수에 최댓값을 넣고 다음 배열 arr[i+1]와 arr[i+2] 중에서 arr[i+1]이 커도 arr[i]가 최대임을 보장하게 한다.

 

 

5. 이후에는 최솟값을 구하는 차례이므로 min 변수를 51(바이트 코인 가격이 최대 50)으로 초기화한다.

 

 

6. 매수를 먼저 하는 것이 최대 이윤을 발생시키므로, 최솟값을 최초로 구한다면 다음으로 최댓값을 찾을 수 있게 isMin 변수로 T/F 설정.

 

 

 

 

즉, 최솟값인 순간과 최댓값인 순간을 따로 저장하면서 최적의 선택을 가지므로 그리디 알고리즘임을 알 수 있다.

 

 

 

전체 코드는 다음과 같다.

 

kotlin version

 

fun main() = with(System.`in`.bufferedReader()) {
    val st = StringTokenizer(readLine(), " ")
    val n = st.nextToken().toInt()
    var w = st.nextToken().toLong()
    val arr = IntArray(n) {readLine().toInt()}

    val minList = mutableListOf<Int>()
    val maxList = mutableListOf<Int>()

    var min = 51
    var max = 0
    var isMin = false
    for(i in 0 until n-1) {
        if(arr[i] < arr[i+1] && min > arr[i]) {
            minList.add(arr[i])
            min = arr[i]
            max = 0
            isMin = true
        }
        if(arr[i] > arr[i+1] && max < arr[i] &&isMin) {
            maxList.add(arr[i])
            max = arr[i]
            min = 51
        }
    }

    var i = 0
    val minSize = minList.size
    val maxSize = maxList.size
    var coin = 0L
    while(i < minSize) {
        //매수
        coin = w / minList[i]
        w %= minList[i]

        //매도
        if(maxSize > i) {
            w += coin * maxList[i]
            coin = 0
        }
        i++
    }
    val result = w + coin * arr[n-1]
    println(result)
}

 

 

java version

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        long w = Long.parseLong(st.nextToken());
        ArrayList<Integer> minList = new ArrayList<>();
        ArrayList<Integer> maxList = new ArrayList<>();

        int[] arr = new int[n];
        for(int i=0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int min = 51;
        int max = 0;
        boolean isMin = false;

        for(int i=0; i<n-1; i++) {
            if(arr[i] < arr[i+1] && min > arr[i]) {
                minList.add(arr[i]);
                min = arr[i];
                max = 0;
                isMin = true;
            }
            if(arr[i] > arr[i+1] && max < arr[i] && isMin) {
                maxList.add(arr[i]);
                max = arr[i];
                min = 51;
            }
        }

        int i = 0;
        int minSize = minList.size();
        int maxSize = maxList.size();
        long coin = 0;

        while(i < minSize) {
            coin = w / minList.get(i);
            w %= minList.get(i);

            if(maxSize > i) {
                w += coin * maxList.get(i);
                coin = 0;
            }
            i++;
        }
        System.out.println(w + coin * arr[n-1]);
        br.close();
    }
}