[BAEKJOON] 11501번 주식

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

11501번: 주식

문제조건

1. 주식하나 사고, 팔고, 아무것도 안하는 것중 하나만 할 수 있다.
2. 각 날마다의 주가가 주어지고, 조건 1 을 반복하면서 최대이익을 구한다.

이 문제는 예시로 시작하는 것이 편할거 같다고 생각한다.

ex) 날 별로 주가가 3, 5, 9일 때 : 3, 5 두 날 전부 주식을 사고, 9일때 주식을 팔면된다
산금액 : 8(3x1 + 5x1)
판금액 : 18(9 x 2) 
최대이익 : 18 - 8 = 10

주식을 매수한날의 수를 팔때 금액에 곱해주면 된다.

그럼 일반적으로 최대이익을 얻기 위해선 어떻게 해야할까?

1,000,000 x 1,000,000 의 복잡도로 완전탐색을 해야하나? 당연히 엄청난 시간이 걸릴거고, 시간초과 또한 날것이다.

탐욕법

부분해가 전체의 최적의 해가 되는 알고리즘이다.

내가 생각한 부분해는 주가가 저렴할때 사고, 비쌀때 파는것이다.

• 그렇다면 아무것도 안하는 것은 언제하냐?
• 저렴하고 비싼것의 판단 기준은 무엇이냐?

가 문제점이다. 여기서 주목해야할점은 우리가 일반적으로 주식을 하는 것이 아닌 하루에 단 1개의 주식만 살수있다는 점이다. 그렇다면 주가를 전부 알고있으므로, 배열을 한번 탐색해서 오름차순으로 정렬이 안될때마다 팔면된다. 그 지점이 바로 최고점에서 팔수있는 금액이기 때문이다. 그리고 가장 큰 금액일때 부터 파는 조건도 같이 고려해야한다.

무조건 오름차순으로 정렬이 안될때 마다 팔아버린다면, 조금 더 뒤에 훨씬 큰값으로 팔 수 있는 경우의 수까지 고려해야하기 때문이다.

ex) 1, 2, 3, 1, 100

위 경우를 보면 극단적이긴하지만 무조건 가장 큰값 까지 기다렸다가 팔아야 하는것을 볼수있다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int t;
int main(){
	cin >> t;
	while (t--) {
		vector<int> v, sub;
		int n, sum = 0, res= 0, top = 0;
		cin >> n;
		
		for (int i = 0; i < n; i++) {
			int a;
			cin >> a;
			v.push_back(a);
		}
		sub = v;
		sort(sub.begin(), sub.end());
		vector<int> cor;
		for (int i = 0; i < n; i++) {
			if (v[i] == sub[sub.size() - 1]) {
				if (cor.empty()) sub.pop_back();
				else {
					res += (cor.size() * v[i] - sum);
					sum = 0;
					sub.pop_back();
				}
				cor.clear();
			}
			else {
				sum += v[i];
				cor.push_back(v[i]);
			}
		}
		cout << res << '\n';

	}
}

뭐지 왜틀렸지

이거 생각한다고 3시간은 쓴거같다,,, 아무리 생각해도 잘못된 부분이 없어보였는데, 바보같은 실수를 했다. 여기서 나의 코드는 가장 큰값보다 작은 수들은 전부 주식을사고, 가장 큰값에서 팔고, 그런다음 원래 가장큰값을 삭제하고, 다음으로 큰값을 가져오는 것이다. 다음으로 큰값이 이미 삭제 된경우라면?

ex) 7 6 9 1 6

위에 내 코드에서 9가 먼저 삭제되고, 그 다음으로 7이선정될건데 7은 이미 팔고 없어진 것이므로 count할 필요가없다!!

for (int buy : cor) 
	if(buy == sub[sub.size() - 1]) sub.pop_back();

이 부분을 추가해주고 실행시켜보니

????????????????????????????

아니 그렇게 어려운 문제 같지도 않은데 계속 틀린다,,,,

이제 코드가 너무 복잡해져서 또 혼자서 가만히 생각해봤다.

뒤에서 부터 접근해보자,,!

입력받은 배열의 뒤에서부터 접근해서 차례대로 최댓값을 구하고 더하고, 만약 최댓값보다 큰값이 앞에 나온다면, 사고 난뒤로 이익을 볼수 없으므로, 아무것도 하지 않으면 된다!

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int t;
int main(){
	cin >> t;
	while (t--) {
		vector<int> v, sub;
		int n, sum = 0, top = 0;
		int res = 0;
		cin >> n;
		
		for (int i = 0; i < n; i++) {
			int a;
			cin >> a;
			v.push_back(a);
		}
		for (int i = v.size() - 1; i >= 0; i--) {
			if (v[i] < top) res += (top - v[i]);
			else top = v[i];
		}
		cout << res << '\n';

	}
}

와 이렇게 간단하게 표현할 수 있다니, 내가 지금 이 문제만 몇 시간을 보는지 모르겠다,,,,

 

????????????!!!!!!!!!!!!!!!!!!!!!!!!!!???????????????????????????????

아 제발요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ,,,,,

이제 약간 시간 낭비느낌이 들어서 그냥 구글링으로 다른 사람들 풀이를 봤다.

그리고 정말 허무함을 느꼈다. 뭐가 잘못되었냐면

바로 이 조건이다. 진짜 허무하다,,,, int는 32bit 정수형으로밖에 표현하지 못하므로 64비트로 늘려주기 위해선 long long자료 형으로 바꿔줘야한다,,,

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int t;
int main(){
	cin >> t;
	while (t--) {
		vector<int> v, sub;
		int n, sum = 0, top = 0;
		long long res = 0;
		cin >> n;
		
		for (int i = 0; i < n; i++) {
			int a;
			cin >> a;
			v.push_back(a);
		}
		for (int i = v.size() - 1; i >= 0; i--) {
			if (v[i] < top) res += (top - v[i]);
			else top = v[i];
		}
		cout << res << '\n';

	}
}

진짜 마지막,,,,, 

그 어느 때 보다 짜릿한 초록색인거 같다 ㅎㅎ