[백준/11501] 주식

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/11501

11501번: 주식

 

2) 설명

일별 주가가 주어졌을 때 주식을 사고 팔아 얻을 수 있는 최대의 이윤을 구하는 문제.

하루에 주식 하나 이하로만 살 수 있다.

2. 풀이

1) 알고리즘

    : 단순 구현

 

2) 풀이 설명

 주식을 매수한 시점보다 미래에 더 높은 가격에 매도할 수만 있으면 그 시점에는 무조건 주식을 매수해야 한다.(파는 건 여러 개 매도할 수 있기 때문)

그래서 해당 시점(i)에 주식을 매수했을 때 가능한 가장 높은 매도가를 기록해놓는 sellPrice 벡터를 사용했다.

그리고 sellPrice[i] - stock[i](매도가 - 매수가)가 양수일 때만 answer (답)에 더해주었다.

 

3. 코드

 

/*
	주식
	단순 구현
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int T;

	cin >> T;

	while(T--){
		long long N, answer = 0;
		cin >> N;
		vector<long long> stock(N);
		vector<long long> sellPrice(N, 0);

		for(int i=0;i<N;i++)
			cin >> stock[i];
		
		for(int i=N-2;i>=0;i--)
			sellPrice[i] = max(sellPrice[i+1], stock[i+1]);

		for(int i=0;i<N;i++)
			answer += max((sellPrice[i] - stock[i]), (long long)0);
		cout << answer << endl;
	}

	return 0;
}

 

4. 느낀점

- 처음에 별 생각 없이 sellPrice를 O(n^2)으로 구했다가 시간초과 났다.. 시간 많이 준다고 해도 (5초) 효율성 고려하자..