[SWEA] 1859. 백만 장자 프로젝트

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&problemLevel=3&problemLevel=4&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1

접근 방법

처음에 스택으로 가격을 저장하다가, 오르막 -> 내리막이 나오는 시점에 파는 방식으로 구현하였으나 실패했다.

마지막날 값을 max로 하여 뒤에서부터 거슬러오면서 max 값보다 작으면 차이를 더해주고, 아니면 max 인덱스를 갱신해주는 방식으로 풀 수 있었다.

풀이

#include<iostream>
#include <algorithm>
 
#define MAX 1000004
using namespace std;
int N;
int arr[MAX];

void init()
{
    fill(arr, arr + MAX, 0);
}

void input()
{
    cin >> N;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }
}

long long solve()
{
    long long result = 0;
    
    int max_day = N-1;
    
    for(int i=N-2; i>=0; i--)
    {
        if (arr[i] <= arr[max_day])
        {
            result += arr[max_day] - arr[i];
        }
        else 
        {
            max_day = i;
        }
    }
    

    return result;
}

void output(int test_case)
{
    cout << "#" << test_case << " " << solve() << "\n";
}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
        init();
        input();
        output(test_case);


	}
	return 0;
}

정리

무조건 앞으로 탐색해야한다는 편견을 버리기

참고

https://velog.io/@d2h10s/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-SW-Expert-Academy-1859-%EB%B0%B1%EB%A7%8C%EC%9E%A5%EC%9E%90-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8