[BOJ/Silver 5] 백준 25644 최대 상승(C++)

문제 링크

https://www.acmicpc.net/problem/25644

25644번: 최대 상승

 

문제

미래를 예측하는 능력이 있는 정균이는 앞으로 N일간 ANA 회사의 주가가 어떻게 변하는지 정확히 예측할 수 있다. 정균이는 예측한 결과를 바탕으로 ANA 회사의 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 최대한의 이득을 얻으려고 한다.

ANA 회사의 앞으로 N일간의 주가를 a1, a2, ..., aN이라고 하자. 정균이가 i번째 날에 주식을 사고, j번째 날에 판다면 aj - ai만큼의 이득을 얻을 수 있다. 정균이는 자금이 넉넉하기 때문에 주가가 아무리 높아도 주식을 살 수 있고, 상황이 여의치 않을 경우 사자마자 바로 팔 수도 있다.

앞으로 N일간 ANA 회사의 주가가 주어졌을 때, 정균이가 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 얻을 수 있는 최대 이득은 얼마일까?

 

입력

첫째 줄에 정수 N(1 ≤ N ≤ 200,000)이 주어진다.

두 번째 줄에 정수 a1, a2, ..., aN이 주어진다. ai(1 ≤ ai ≤ 10^9)는 i번째 날의 ANA 회사의 주가이다.

 

출력

ANA 회사의 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 얻을 수 있는 최대 이득을 출력한다.

 

예제 입력 1

5
4 2 3 1 5

예제 출력 1

4

예제 입력 2

3
3 2 1

예제 출력 2

0

예제 입력 3

4
7 1 2 6

예제 출력 3

5

 

알고리즘 분류

• 그리디 알고리즘

 

풀이

ANA 회사의 주가를 N번째 날부터 거꾸로 탐색하며 최댓값을 초기화해주는 동시에 주가의 최댓값과 i번째 날의 주가 ai의 차이의 최댓값을 구한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
vector<int> A;
int Max_A;
int Answer;

void input() {
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
}

void settings() {
    for (int i = (N - 1); i >= 0; i--) {
        int Now = A[i];
        Max_A = max(Max_A, Now);
        Answer = max(Answer, Max_A - Now);
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}