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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc

SW Expert Academy

---

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;
int main(void)
{
	int size;
	int len;
	vector<ll> v;
	ll quan,buy,sell,num;
	int max,index;
	scanf("%d",&size);
	for(int i = 0; i < size; i++)
	{
		max = -1;
		quan = 0; buy = 0; sell = 0;
		scanf("%d",&len);
		v.resize(0);
		for(int x = 0; x < len; x++)
		{
			scanf("%lld",&num);
			v.push_back(num);
		}
		
		max = v[len-1];
		for(int x = len-1; x >= 0; x--)
		{
			if(max > v[x]){
				sell += max - v[x];
			}else{
				max = v[x];
			}
		}
		printf("#%d %lld\n",i+1,sell);
		
		
	}
	return 0;
}

---

해결 방법:

맨 뒤의 원소를 max로 두고, 계속 뒤부터 보면서 max보다 작으면 이득을 보고 판 것처럼 처리한다.

그렇지 않으면 max값을 바꿔준다.

​

시행착오 :

long long 이 나올 수 있다는건 처음에 읽었을때 알았다. 근데 난 정방향 탐색을 했었다.

​

1. 앞보다 뒤가 크면 사고, 뒤에가 더 크면 판다. 는 방식으로 했다.

1 1 3 1 1 4 를 하면 반례가 생긴다.

​

2. 최댓값을 scanf때 찾고, 그 최댓값 전까지 다 사고 그 뒤에는 또 1번처럼 하기로 했다.

1 1 3 1 1 4 에서 잘 된다.

하지만 1 1 5 1 3 2 4 에서 안된다. (1 3 에서 팔아버린다.)

​

3. 그렇다면 여기서 2가지 방법이 있다.

3-1. 앞부터 탐색하는 경우

(시작 ~ 처음 최댓값 index) 범위에서 구매 및 판매.

(처음 최댓값 index+1 , 끝범위) 에서 다시 재귀함수처럼 최댓값 찾고, 다시 사고, 그 다음 범위에서 또 함수..

이런 방법이 있다.

이렇게 하면 뭐가 안좋은가? 10 9 8 7 6 5 4 3 2 1 처럼 역순이면 O(n^2) 이다..

​

3-2 뒤부터 탐색하는 경우.

앞으로 탐색하는 문제는, 처음 최댓값 이후 뒤에서 또 다른 최댓값을 찾는 작업이 필요했다.

하지만 뒤에서 찾게되면 음.. 설명을 어떻게 해야할지 모르겠는데

3-1의 불필요한 최댓값을 찾는과정이 필요가 없다. 그냥 뒤부터 찾으면 항상 최댓값인데..

​

=====END

​