[SWEA] 백만장자 프로젝트(Difficulty 2)

👀 문제 설명

문제

로그인해야 문제를 볼 수 있다

 

✍🏻풀이

이 문제는 앞에서부터 접근하면 시간 초과가 날 수 있는 문제이다.

뒤에서부터 접근하면서 가장 큰 값을 max_budget에 넣는다.

현재 값이 max_budget보다 작으면 max_budget - 현재값을 ans에 더해가며 답을 구하면 된다.

 

코드

#include <stdio.h>
#include <iostream>

using namespace std;

int num[1000002] = { 0, };

int main(int argc, char** argv) {
    int T;
    
    cin >> T;
    
    for (int i = 0; i < T; i++) {
        int N;
        long long ans = 0;
        
        cin >> N;
        for (int j = 0; j < N; j++) {
            cin >> num[j];
        }
        
        int max_budget = num[N - 1];
        
        for (int j = N - 1; j >= 0; j--) {
            if (max_budget >= num[j]) {
                ans += (max_budget - num[j]);
            }
            else {
                max_budget = num[j];
            }
        }
        
        cout << "#" << i + 1 << " " << ans << endl;
        for (int j = 0; j < N; j++) {
            num[j] = 0;
        }
    }
    
    return 0;
}