백준 11501 c++ "주식" -PlusUltraCode-

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

[필자 사고]

처음에 필자는 stack을 이용하여 증가하다가 감소하는 부분마다 갱신해주는 형태로 계산했다.

그러나 문제가 틀렸고 곰곰히 생각해보니 굳이 증가하다가 감소하는 부분마다 팔지 않아도 된다는 사실이다.

이러한 이유로 뒤에서부터 탐색을 시작하여 갱신해주는 형태로 문제를 해결했다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

---

main 함수

1. 입력 처리
   • 첫 줄에서 테스트 케이스 개수 T를 입력받습니다.
   • 각 테스트 케이스마다 정수 N(날짜 수)을 입력받고, 길이가 N인 배열에 가격 정보를 저장합니다.
2. 이익 계산
   • 결과를 저장할 변수 resultPrice를 0으로 초기화합니다.
   • 배열의 마지막 날부터 거꾸로 순회하면서 최대 가격을 추적합니다.
   • 현재 가격이 최대 가격보다 크면 최대 가격을 갱신합니다.
   • 현재 가격이 최대 가격보다 작으면, 그 차이만큼 이익으로 더합니다.
   • 이렇게 하면 "뒤에서 앞으로 보았을 때 가장 비싼 날에 팔고 그 이전에 산다"라는 조건을 자연스럽게 만족할 수 있습니다.
3. 결과 출력
   • 하나의 테스트 케이스가 끝나면 누적된 최대 이익 resultPrice를 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int T;
int N;
stack<int> myStack;
long long resultPrice = 0;



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

    cin >> T;
    while (T--) {
        cin >> N;
        vector<int> arr(N);
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }

        resultPrice = 0;
        int maxPrice = 0;
        for (int i = N - 1; i >= 0; i--) {
            if (arr[i] > maxPrice) {
                maxPrice = arr[i];
            }
            else {
                resultPrice += (maxPrice - arr[i]);
            }
        }

        cout << resultPrice << "\n";
    }
}