[백준, C++] 11501 - 주식

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

11501번: 주식

 

문제 분석

문제의 주인공은 미래의 주가를 예측할 수 있다. 그리고 그 예측이 항상 맞아떨어진다(부럽다). 문제의 주인공 홍준씨는 매일 3가지 중 하나의 행동을 한다고 한다. 주식을 하나 사거나, 원하는 만큼 가진 주식을 팔거나, 아무것도 하지 않는 것이다. 근데 홍준씨는 바보(?)라서 자신이 어떻게 행동을 해야 최대의 이익을 낼 수 있는지는 모른다. 그래서 우리는 홍준씨가 최대의 이익을 얻을 수 있도록 언제 사고 언제 팔면 되는지를 코드로 해결해줘야 한다. 출력으론 홍준씨가 벌 수 있는 최대 수익을 뽑아내면 된다.

 

문제 내용을 쓱 읽어보면, 이 문제는 '최대의 이익을 내는 것'이 관심사이다. 최대의 효율을 뽑아내고자 하는 것, 최대한 욕심내는 것, 그리디 알고리즘으로 풀 수 있겠다고 생각했다. 그렇다면 "어떻게 그리디하게 답을 구해낼 것인가 ?" 가 문제이다.

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

int t;
int n;
int price;
vector<int> prices;
long long result;

void reset() {
    prices.clear();
    result = 0;
}

void getInput() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> price;
        prices.push_back(price);
    }
}

void solve() {
    int maxPrice = 0;

    for (int i = prices.size() - 1; i >= 0; i--) {
        int price = prices[i];

        if (price > maxPrice) {
            maxPrice = price;
        } else if (price == maxPrice) {
            // 아무것도 하지 않는다.
        } else if (price < maxPrice) {
            result += (maxPrice - price);
        }
    }
}

void printResult() {
    cout << result << "\n";
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> t;
    while (t--) {
        reset();
        getInput();
        solve();
        printResult();
    }
}

 

코드 설명

처음에 간단하게 생각한 방법은, 주가 배열을 순회하다가 주가가 상승했을 때 파는 것이었다. 근데 이렇게 풀자니 문제가 있는데, '앞으로도 쭉 상승할 것인지' 를 알기 위해서는 결국 한 바퀴를 다 돌아야만 알 수 있다는 것이다. 예를 들어보자면,

 

1 2 3 4 2 3 4 5

 

이렇게 주가 배열이 있다고 쳐보자. 그러면 4일차에 주가가 '4' 일 때 파는 게 이득처럼 보인다(4일차까지만 본다면). 그렇지만 실제로는 주가가 '4' 인 7일차까지 계속 사놓다가 파는 것이 최대의 이득을 볼 수 있는 방법이다. 결국 앞에서부터 순회를 하게 되면 '최적의 해' 인 것 같지만 그렇지 않을 수 있다는 것이 문제이다. 즉, '최고점' 처럼 보이지만 사실은 최고점이 아닐 수 있다는 얘기가 된다. 또한 순회를 여러 번 할 수 있기 때문에 문제가 발생하기도 한다. 주가는 최대 100만 개가 주어질 수 있기 때문에 여러 번 순회하는 것이 부담스럽다.

 

이를 해결하고자, 주가 배열을 뒤에서부터 앞으로 읽어나가는 방법을 생각했다. '팔아야 할 날' 이 언제인지를 뒤에서부터 읽으면서 찾는 것이다. 방법은 이렇다.

 

1. 가장 마지막 날의 주가를 최고가라고 생각한다. 앞으로 최고가보다 낮은 주가가 등장하면, 그 낮은 주가에 주식을 매입해서 '최고가' 라고 메모해둔 그 값에 매도할 것이다. 반대로 최고가보다 높은 주가가 등장하면, 최고가를 갱신할 것이다. 즉 '팔아야 하는 날' 을 계속 업데이트할 것이라는 얘기다.

 

2. 가장 마지막 날부터 이전 날들의 주가를 읽어나가면서 '지금까지의 최고가' 와 '현재 주가' 를 비교한다. 아래와 같은 3가지 케이스가 나타날 수 있다.

 

    1) 지금까지의 최고가 > 현재 주가

    2) 지금까지의 최고가 == 현재 주가

    3) 지금까지의 최고가 < 현재 주가

 

1번의 경우, 현재 주가에 사서 지금까지의 최고가에 파는 것이다. 2번의 경우는 아무것도 하지 않아도 된다. 왜냐면 지금 주가로 사서 최고가에 팔아봤자 이득은 0이기 때문이다. 3번의 경우는 지금까지의 최고가를 현재 주가로 갱신한다. 즉, 현재보다 이전의 시점에 산 주식은 굳이 현재 주가보다 낮은 '지금까지의 최고가' 에 팔 이유가 없기 때문이다.

 

추가로, 결과에 해당하는 result 변수는 long long으로 선언했다. 내 기억으로는 int는 21억 언저리까지 표현이 가능한데, 주가는 최대 100만 개가 주어지고 주가는 최대 1만 이기 때문에 21억을 초과할 수 있을 것이라 생각했다.

 

문제 해결 로직 자체는 쉽지만, 이 로직을 생각하는 것이 오래 걸렸다. 굉장히 쉬운 문제라 생각했지만 은근히 오래 걸려서 아직도 나는 부족하다고 느꼈다. 나는 가짜 플래티넘이다.