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

문제 소개

11501번: 주식

 홍준이는 어느 주식의 날짜별 주가를 알 수 있다. 근데 계산을 못한다. 그래서 언제 사서, 언제 팔면 최대 이익을 얻을 수 있는지 계산을 부탁했다.

 

 예를 들어 설명하면 다음과 같다.

 

 5일 동안의 주가 변화가 1, 2, 5, 3, 2원일 때 첫째 날, 둘째 날 주식을 사면 사흘째에 5원에 판매함으로써 9원의 이익을 얻을 수 있다.

---

문제 풀이 전략

 

기획

 

 이 문제를 해결하는 방법은 매우 간단하다. n일에 주식을 샀을때, 그 가격을 a[n]이라고 가정하자. n ≤ m인 m 중에서, 가장 큰 a[m] 값을 M이라 할 때, M - a[n]이 n일에 주식을 샀을 때 얻을 수 있는 최대 이익이다. 다시 말해서, 미래에 기대할 수 있는 최댓값에서 현재 값을 빼준 값들을 모두 더하기만 하면 된다.

 

 역시 말로만 들으면 무슨 이야기인지 알기 어렵다. 아래의 그림을 보면서 이해해보자.

 

 입력으로 n = 8, 주가는 각각 1, 3, 10, 1, 2, 1, 6, 4원이 주어진 상황이다. 아직 탐색을 시작하지 않고, 데이터 입력만을 받은 상태라 할 수 있다.

 

 마지막 날인 8일부터 탐색을 시작한다. 이 시점에서는 첫째 날이던, 나흘 째던 미래에 기대할 수 있는 최고 가격은 4원이라고 생각한다. 8일째에 주식을 구매했다 쳤을 때, 구매가는 4원이고 미래 최고가도 4원이므로, 이 시점에서의 최대 이익은 0 + 4 - 4 = 0원이다.

 

 7일까지 탐색을 완료하고 나면, 미래 최고가는 6원으로 갱신된다. 하지만 최대 이익은 여전히 0원.

 

 6일까지 탐색을 완료화면 위 그림과 같다. 6일 차의 주가는 1원인데 미래 최고가는 6원이므로, 이 날 주식을 사면 5원의 이익을 얻을 수 있다. 당연하게도 1 < 6 이므로 미래 최고가는 갱신되지 않는다.

 

 5일 차와 4일 차의 탐색도 6일 차와 과정이 유사하다. 미래 최고가는 갱신되지 않지만, 미래 최고가와 현재 주가의 차이만큼 최대 이익에 계속해서 더해준다.

 

 이러한 과정을 계속해서 반복하면, 이 테스트 케이스에서 얻을 수 있는 최대 이익은 30원이라는 것을 알 수 있다.

 

 

 

설계

 

 대단한 자료구조가 필요하지는 않다. 다만 입력을 받을 때마다 계산하는 것이 아닌, 전체 입력을 받아놓고 뒤에서부터 탐색하는 방법인지라 길이 100만의 정수형 배열이 필요하다.

 

 

 

주의사항

 

그날그날의 이익이 최대 10000원까지 날 수 있으므로 최대 이익값이 1000억이 될 수 있다. 그러므로 정답을 저장하는 자료형은 long long 자료형을 사용하여야 한다.

 

 

 

---

소스 코드

 

#include <iostream>
using namespace std;

int t, n;
int arr[1000001];

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

    cin >> t;

    for(int i = 0; i < t; i++)
    {
        long long ans = 0;
        int best = 0;
        cin >> n;

        for(int j = 0; j < n; j++)
            cin >> arr[j];

        for(int j = n - 1; j >= 0; j--)
        {
            if(best < arr[j])
                best = arr[j];
            else
                ans += best - arr[j];
        }

        cout << ans << "\n";
    }

    return 0;
}

---

테스트 케이스

 

[예제 1]
입력:
3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

출력:
0
10
5



[예제 2]
입력:
1
8
1 3 10 1 2 1 6 4

출력:
30