[BOJ][C++] 백준 17521번 : Byte Coin

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

17521번: Byte Coin

 

문제

국제자본부동산회사(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는 그렇게 크지 않지만 최종 현금은 매우 커질 수 있음에 주의하자.

 

풀이

#include <iostream>

using namespace std;

int main () {
    
    //입력
    int n;
    long long w;
    cin >> n >> w;
    int s[n];
    for(int i=0; i<n; i++)
        cin >> s[i];
    
    //세팅
    long long coin = 0;
    for(int i=0; i<n; i++){ //이후에 나오는 값이 첫째날보다 크다면 풀매수 하고 시작, 작다면 그냥 바로 시작
        if(s[0] < s[i]){
            coin += w/s[0];
            w -= coin*s[0];
            break;
        }
        else if(s[0] > s[i])
            break;
    }
    
    //계산
    for(int i=1; i<n-1; i++){  //인덱스가 1부터 시작하고 n-1에서 끝난다는 점 주의
        if(s[i] > s[i+1] && s[i] > s[i-1]){
            //극댓값 -> 풀매도
            w += coin*s[i];
            coin = 0;
        }
        if(s[i] < s[i+1] && s[i] < s[i-1]){
            //극솟값 -> 풀매수
            coin += w/s[i];
            w -= coin*s[i];
        }
    }
    
    //마지막날 풀매도
    w += coin*s[n-1];
    
    //출력
    cout << w;
    
    return 0;
}

#include <iostream>

using namespace std;

int main () {
    
    //입력
    int n;
    long long w;
    cin >> n >> w;
    int s[n];
    for(int i=0; i<n; i++)
        cin >> s[i];
    
    //세팅
    long long coin = 0;
    
    //계산
    for(int i=0; i<n; i++){
        if(s[i] > s[i+1] ){
            //다음날보다 크면 -> 풀매도
            w += coin*s[i];
            coin = 0;
        }
        if(s[i] < s[i+1]){
            //다음날보다 작으면 -> 풀매수
            long long tmp = w/s[i];
            w -= tmp*s[i];
            coin += tmp;
        }
    }
    
    //마지막날 풀매도
    w += coin*s[n-1];
    
    //출력
    cout << w;
    
    return 0;
}

 

TIL

알고리즘 문제풀이는 최대한 쉽게 접근하자.

뇌로 수학문제 푸는것과는 다른 방식으로 생각해야한다.

컴퓨터는 생각보다 멍청하다