백준 11501 - 주식 (C++)

---

1 - 3 - 10 - 5 - 2 - 3 이렇게 6일의 주식이 주어졌다고 가정해보자.

 

각 일자를 기준으로, 주식을 구매했다면 뒤의 날중 가장 비싼 날에 판매하는 것이 가장 이익이 극대화 될 것이다.

 

맨 첫날의 주식의 경우, 1원이기 때문에 뒤의 날중 가장 비싸게 팔 수 있는 3번째날에 판매하는 것이 이익이 최대일 것이다.

 

반면, 4번째 날의 경우, 뒤의 날중 5원 이상으로 팔 수 있는 날이 없다.

그러므로 4번째 날의 주식은 구매하지 않는 것이 가장 좋다.

 

정리해보자면 뒤의 날중 최대 주식 가격이 구매 가격보다 비싸다면 그 날 판매해야하고,

구매 가격보다 저렴하다면 주식을 구매하지 말아야 한다.

 

이를 위해, 배열의 원소마다 뒤쪽의 값을 모두 검사해서 최대값을 구해서 확인할 수도 있겠지만, N의 최대가 1,000,000이기 때문에, 시간초과가 발생할 수 밖에 없다.

 

본인은 이런 방식을 사용하였다.

 

먼저, MaxStock이라는 변수를 하나 선언하였다.

1 - 3 - 10 - 5 - 2 - 3 의 배열이 주어졌다면, 뒤에서 부터 역으로 검사하며 MaxStock을 계속 갱신하며 이익을 더해주었다.

 

MaxStock = 0;

Profit = 0;

 

6일차 - 3원 ( MaxStock < 3) -> MaxStock = 3;

6일차에선, MaxStock보다 주식의 가격이 높기 때문에 3원으로 갱신해주었다.

 

5일차 - 2원 (MaxStock> 2) -> 갱신 X

Profit += MaxStock - (2원); 

 

5일차에선 MaxStock이 주식 가격보다 높기 때문에, 값을 갱신하지 않았다.

이 때, 5일차의 주식은 뒤의 날중 가장 비싼 주식의 가격인 MaxStock의 값에 주식을 판매하는 것이 가장 효율적이기 때문에, 주식을 MaxStock 가격에 판매하였다.

 

4일차 - 5원 (MaxStock < 5) -> MaxStock = 5;

3일차 - 10원 (MaxStock < 10) -> MaxStock = 10;

2일차 - 3원 (MaxStock > 3) -> 갱신X , Profit += MaxStock - (3원); 

1일차 - 1원 (MaxStock > 1) -> 갱신X , Profit += MaxStock - (1원); 

 

이처럼, 뒤에서부터 MaxStock을 최대값으로 갱신하며 앞으로 탐색하게 되면 주식은 반드시 MaxStock에 판매하는 것이 이득일 수 밖에 없다. (MaxStock은 뒤의 날중 최대 가격이기 때문에)

 

또한, 뒤의 날중 최대 가격인 MaxStock이 현재 가격보다 저렴하다면, 주식을 판매하지 않고 최대 주식 가격을 갱신하기 때문에 더 저렴한 가격에 주식을 팔아 손해보는 일도 발생하지 않는다.

 

이렇게 로직을 짜면, 1번의 반복문만 돌면 되기 때문에 O(n)의 시간복잡도를 가지게 된다.

 

풀이 코드

---

 

먼저 입력이다. TestCase의 수를 입력받고, TestCase의 수 만큼 출력해야하는 답이 존재하기 때문에 답을 보관할 vector를 선언하였다.

int NumOfTestCase = 0;
std::cin >> NumOfTestCase;

std::vector<long long> Answers;
Answers.reserve(NumOfTestCase);

 

다음은, 총 며칠이 주어지는 지와 주식 가격에 대한 정보를 입력받았다.

그 이후, 위에서 설명한 것과 같이 맨 뒤에서부터 앞으로 탐색하며 MaxStock의 가격을 갱신하였고,

현재 주식 가격보다 MaxStock이 더 비싸다면 주식을 판매하여 이익을 증가시켰다.

for (int i = 0; i < NumOfTestCase; i++)
{
    int Days = 0;
    std::cin >> Days;

    std::vector<int> Stocks(Days);
    for (int i = 0; i < Days; i++)
    {
        std::cin >> Stocks[i];
    }

    long long MaxStock = 0;
    long long Profit = 0;

    for (int i = Days - 1; i >= 0; i--)
    {
        if (MaxStock < Stocks[i])
        {
            MaxStock = Stocks[i];
        }
        else
        {
            Profit += MaxStock - Stocks[i];
        }
    }

    Answers.push_back(Profit);
}

 

마지막으로 출력해주면 된다.

for (int i = 0; i < NumOfTestCase; i++)
{
    std::cout << Answers[i] << "\n";
}

 

 

여기서 주의해야 할 점은 답을 int형이 아닌 long long 형으로 저장해야 한다는 것이다.

int형으로 저장하고 출력하게 되면, 오답처리가 된다.