11501 주식

11501 주식 https://www.acmicpc.net/problem/11501

홍준이가 할 수 있는 행동은 3가지중 한가지를 할 수 있다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

홍준이가 벌 수 있는 최대이익을 구하는 문제이다.

N이 1,000,000이나 되어서 $O(N)$ 또는 $O(Nlog(N))$으로 해결해야한다.

처음에는 단순히 주가가 감소하기 전 시점에서 파는걸로 풀었다.

현재까지 주가를 누적시켜서 나중에 파는 거기때문에 반례가 존재한다. 

({3, 2, 10}은 첫째날, 둘째날 주식을 사서 마지막날 팔면 15의 최대이익을 얻는다.)

두 번째로 dp로 구현하여 풀었지만 시간초과가 나왔다. 

사실 방법은 간단하다.
현재 값보다 나중 값이 더 클 경우는 무조건 이득이 있기 때문에 사는것이 낫다.
배열을 뒤에서 부터 비교하는것이 쉽게 구현된다.

#include <cstdio> #define max(a,b) ((a)>(b)?(a):(b)) int N; int arr[1000000]; int main() {     int T;     scanf("%d", &T);     while (T--) {         scanf("%d", &N);         for (int n = 0;n < N;n++) scanf("%d", &arr[n]);         long long ans = 0;         int ma = arr[N - 1];         for (int n = N - 2;n >= 0;n--) {             if (arr[n] < ma)                 ans += 1LL*(ma - arr[n]);             else ma = arr[n];         }         printf("%lld\n", ans);     }     return 0; } Colored by Color Scripter

cs