[백준][C++] 11501. 주식

입력으로 날 수와 각 날의 주가가 주어졌을 때 최대 이익을 구하는 문제이다.

 

처음 이 문제를 봤을 때 제일 먼저 생각난 방법은 DP였다.

하지만 DP로 하기에는 주어진 숫자가 너무 크기도 했고... 

단순히 감소하는 시점에 팔아버리는 것으로 구현하면

뒤에 더 고점이 나왔을 때 반례가 존재하기 때문에 이 방식은 포기했다.

 

 

내림차순으로 sorting한 후에 이익을 계산해볼까도 했지만,

이 경우 sorting시 순서도 같이 기억해야했기 때문에 포기..

 

 

결국 내가 선택한 방법은

뒤에서부터 반복문을 돌아서,

이전까지의 최대 주가보다 현재 주가가 더 크면 최대 주가를 갱신하고, 

반대로 현재 주가가 더 작으면 차익만큼을 플러스하는 식으로 구현했다.

 

 

예를 들어 주가가

cost[8] = 4 1 2 4 5 6 2 2

이렇게 있다고 하면,

 

뒤에서부터 반복문을 돌 때, 최대 주가의 초기값은 cost[7] = 2이다.

그 다음 cost[6] = 2는 값이 같으므로 그대로 넘어가고,

cost[5] = 6은 2보다 크므로 최대 주가를 6으로 갱신한다.

그 다음부터는 모두 6보다 작으므로,

최대 이익은 (6 - 5) + (6 - 4) + (6 - 2) + (6 - 1) + (6 - 4) = 14가 된다.

 

 

처음에 아무 생각 없이 int 타입을 사용했다가 8%에서 계속 틀렸다;;

날의 수 n이 1000000이고 날별 주가의 최대값이 10000이므로

최대이윤의 데이터 타입은 반드시 long long 타입으로 지정해주자...

// 11501_주식.cpp 
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#include <iostream>
#define MAX 1000001

typedef long long ll;

int tc; // test case
int n; // 날의 수
int cost[MAX] = { 0, }; // 주가

int main()
{
	scanf("%d", &tc);

	for (int i = 0; i < tc; i++) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &cost[i]);
		}

		int max_cost = cost[n]; // 최대 주식 가격
		ll max_benefit = 0; // 최대 이윤 (long long 타입)
		for (int i = n - 1; i > 0; i--) {
			if (max_cost < cost[i]) max_cost = cost[i]; // 최대 주가 갱신
			else if (max_cost > cost[i]) {
				max_benefit += (ll)(max_cost - cost[i]); // 최대 이윤 계산
			}
			else continue; // 값이 같은 경우 pass
		}

		printf("%lld\n", max_benefit);
	}
}