[백준/Baekjoon] 11501 주식 C++ :: Greedy

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

11501번: 주식

---

1. Logic

- 해당 문제는 주어진 배열을 앞에서 부터 풀이하게 될 경우 최댓값까지 배열을 돌고 또 최댓값을 구해서 배열을 돌아야해서 이중 for문을 사용하게 되어 시간복잡도가 O(n^2)이지만 뒤에서부터 풀이하게되면 다음값을 보고 최댓값인지 알 수 있기 때문에 O(n)으로 풀 수 있다.

 

최악의 경우를 생각 해 봤을 때 10000 *999999 곱하게되면 int 의 범위를 훨씬 넘기 때문에 long long type으로 선언해 주는 것도 잊지 말아야 한다.

 

뒤에서부터 풀면 쉽게 풀 수 있다는 아이디어를 떠올리는 것 빼고는 어렵지 않았다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;

    while(t--) {
        vector<int> vec;
        long long profit = 0;
        int maxValue = 0;
        int n;

        cin >> n;

        for(int i = 0; i < n; i++) {
            int a;
            cin >> a;
            vec.push_back(a);
        }


        for(int i = n - 1; i >= 0; i--){
            if(vec[i] < maxValue) {
                profit += (maxValue - vec[i]);
            }
            else {
                maxValue = vec[i];
            }
        }
        cout << profit << "\n";
    }
}

 

 

---

 

 

3. Feedback

 - 문제가 너무 어렵거나 시간 복잡도를 훨씬 뛰어넘는 문제를 파악한 후에는 뒤에서 부터 풀이하는 것을 고려해 봐야겠다.