[BOJ/백준 11501][C++] 주식

문제

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

백준 11501

백준 11501

 

문제 내용

날 별로 주식의 가격이 주어진다.

이때 우리는 주식을 사거나 / 팔거나 / 아무것도 안 하거나 3가지 중에 골라야 한다.

최대 이익을 만들어 결과를 출력하면 된다.

 

문제 풀이

문제를 읽고 나서 가장 먼저 떠오르는 것은 앞에서부터 차례로 확인해나가는 방법이었다.

현재 구입하는 시점 이후에 가장 비쌀 때 팔아버리면 된다.

현재 구입 시점이 가장 비싸다면 사지 않으면 된다.

 

다만, 이 방법은 구현하기가 어려웠다.

현재 구입하는 시점 이후 중, 가장 비싼 때를 찾기가 어렵기 때문이다.

 

그래서 뒤에서부터 확인하기로 했다.

그렇게 되면 가장 비쌀 때를 먼저 확인하고 이후에 주식을 살 수 있다.

 

코드

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


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int testcase;
	cin >> testcase;

	for (int i = 0; i < testcase; i++) {
		int day; cin >> day;
		vector<int>money(day);
		for (int j = 0; j < day; j++) cin >> money[j];
		
		//문제 해결 => 뒤에서부터 탐색 하자
		//구입 시점 이후에서 가장 비쌀 때를 미리 확인하고 삼
		//손해보게 파는것 보단 아예 안 사는게 나을 때도 있다
		long long result = 0; //int로 선언하면 틀린다.
		int k = day - 1;
		for (int j = day-2; j >= 0; j--) {
			if (money[k] > money[j]) result += money[k] - money[j]; //이익 계산
			else k = j; // 이 경우에 money[k]가 가리키는 값이 더 커진다. (max값 찾는 과정)
		}
		
		//결과 출력
		cout << result << '\n';
	}
}

 

문제 코드 설명

1) 문제 해결

for문 안의 if 조건을 확인해보자.

money[k] > money[j] 라는 뜻은, 주어진 날들 중 오른쪽 끝에 가까운 날의 주가가 더 높다는 것이다.

그렇다면 j 날에 주식을 사서 k날에 팔아버리는 것이 이득이라는 소리이다.

또한 j날의 가격이 더 낮기 때문에 뒷부분에서 주가가 가장 비쌀 때는 여전히 k날이다.

 

위 조건을 만족하지 못하고 else문으로 넘어가게 되면, 최댓값이 바뀌었다는 소리이다.

따라서 최대값이 존재하는 날을 나타내는 변수인 k를 j 날로 바꾸어야 한다.

(max 값을 가지는 날을 갱신하는 것)