SWEA 1859. 백만 장자 프로젝트

SWEA 1859. 백만 장자 프로젝트 문제를 해결해보았다.

처음에는 전체 탐색으로 해보았는데 역시나 시간초과가 나서 ㅠ...

방법을 생각해보는데 이래저래 해도 머리가 잘 안돌아가서 솔루션 검색하려는데 갑자기 최댓값이 생각이나서 최댓값을 활용했다.

최댓값이 존재하면 최댓값 전까지의 값들은 전부 더하면 되기 때문에 전체 탐색인 이중포문 n^2을 하지 않더라도 for 문 한개로 해결할 수 있었다. (물론 for문안에 최댓값을 찾는게 메소드가 있긴해서 정확한 Big O는 모르겠지만 시간초과는 나지않는다)

최댓값을 찾는 방법은 algorithm header의 max_element를 찾아서 사용했다. 

값이 int의 최댓값을 초과해서 실패해서 output은 long long으로 선언 해주었다. 오랜만에 해서 왜 오류가 나는지 됴무지 이해가 가지 않았지만 알고나서 매우 ㅂㄷㅂㄷ..

 

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char **argv)
{
    int test_case;
    int T;

    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case)
    {
        int day;
        cin >> day;
        vector<int> prices;

        long long output = 0;

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

        auto it = max_element(prices.begin(), prices.end());
        int max = *it;
        for (int i = 0; i < day - 1; i++)
        {
            if (prices[i] == max)
            {
                auto it = max_element(prices.begin() + i + 1, prices.end());
                max = *it;
            }
            else{
                output += max - prices[i];
            }
        }

        cout << "#" << test_case << " " << output << endl;
    }
    return 0; //정상종료시 반드시 0을 리턴해야합니다.
}