주식( BOJ 11501 )

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

11501번: 주식

 

문제 파악하기

주식을 어느 날에 팔아야 최고 이익이 나는지 파악하는 문제입니다. 입력 값이 최대 1,000,000개이기 때문에 왠만하면 단순 반복문으로 알고리즘을 설계해야 한다는 점에 유념한다면 어렵지 않게 문제를 풀 수 있습니다.

 

문제 해결하기

문제를 풀기 위해서는 언제 주식을 팔아야 하는지 알아야 합니다. 최고의 이익을 내기 위해서는 가장 주가가 비싼 날에 판매를 해야합니다. 그렇다고 단순히 우선순위 큐를 사용하기에는 입력 값이 너무 많습니다. 이 때, 우리가 주목할 점은 바로 주가의 가격입니다. 문제에서 주가는 최대 10,000까지의 범위를 가진다고 했습니다. 그렇기에 우리는 주가의 날짜를 저장하기 위한 배열을 만든 다음, 해당 주가를 가진 날짜를 저장하고, 입력된 날짜 중 큰 주가를 가진 날부터 주식을 판매하면 최대 이익을 구할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
typedef long long int lint;
 
int T, N, t;
lint pSum[1000010];
 
int idx;
lint ret;
int value[10010];
 
int main() {
    scanf("%d", &T);
    while(T--) {
        memset(value, 0, sizeof(value));
        ret = idx = 0;
        
        scanf("%d", &N);
        for(int i=1;i<=N;i++) {
            scanf("%d", &t);
            value[t] = i;
            pSum[i] = pSum[i-1]+t;
        }
        
        for(lint i=10000;i>=1;i--) {
            if(!value[i] or value[i] < idx) continue;
            
            ret += (value[i]-1 - idx)*i - (pSum[value[i]-1] - pSum[idx]);
            idx = value[i];
        }
        
        printf("%lld\n", ret);
        
    }
}
 

후기

만약 주가의 범위가 크다면 뒤에서부터 값을 확인하면서 최고 주가만큼 이익을 더하는 알고리즘을 사용해야 합니다. 다만, 10,000까지의 주가를 가지고 있기에 배열의 인덱스를 활용하는 알고리즘을 소개할 때 유용하다고 생각합니다.