[ACM-ICPC][BOJ] 11501 - Stock 문제풀이

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2015 본선 문제인

BOJ 11501 Stock 문제풀이를 해보겠습니다.

---

[문제해석]

당신은 주식을 1개 사거나, 그동안 사온 주식을 팔거나, 아무것도 안 하거나 3가지 일 중 하나만 하루에 행동할 수 있다. 이때, N일 동안의 주식 가격이 주어졌을 때, 얻을 수 있는 최대 이익을 구하는 알고리즘을 구현하라.

 

Ex)

[ 1 1 3 5 4 2 3 ] 7일 동안 주식 가격이 주어졌다고 가정해보자.

1일 차, 2일 차, 3일 차는 4일 차인 주식 가격이 최대치인 5일 때 팔아야 되고,

6일 차는 7일 차인 주식 가격이 3일 때 팔아야 된다.

즉, i 일차 주식이 얻을 수 있는 최대 이익은 (i + 1) ~ 마지막 날까지 중 가장 주식 가격이 큰 날 팔아야 된다.

 

[쓴이생각]

문제는 생각보다 간단하지만, 알고리즘을 생각해내기까지 굉장히 오래 걸렸다.

 

처음 든 생각은 '무식하게 구해보자.'였다.

앞에서부터 순회하며 각각의 날에 대해 최대 이익을 구했다.

i 번 째 날의 최대 이익을 구하기 위해, (i + 1 ) ~ 마지막 날까지 순회하며 Max를 구해 최대 이익을 구했다.

당연히, O(n^2) 으로 시간 초과를 했다.

 

그다음 생각은 '뒤에서부터 순회를 해보자.'였다.

뒤에서부터 순회하면 Max를 구하기 위해 따로 순회할 필요가 없다.

예를 들어, [5 7 9 11] 이라고 해보자. 9 입장에서는 뒤에서부터 찾아온 11이라는 Max값이 중요하고, 5, 7 입장에서도 뒤에서부터 가져온 11이라는 Max 값이 중요하다.

즉 뒤에서부터 순회하면, Max 값을 그냥 순회할 때, If 문 하나로 계속 찾아줄 수 있다.

 

[알고리즘설계]

뒤부터 순회하며 Max는 마지막 날의 이익부터 시작해서 더 큰 이익을 저장해나가며 갱신한다.
Result에는 i번 째 날의 주식 값보다 Max가 더 크다면 Max - dp_list[i] 를 더해가며 쌓는다.

다음과 같이 예시를 통해 생각해보자.
index      0  1  2  3 4 5 6 7 8 9 10
Number    1  4  10 8 7 4 7 5 2 3 1
Max         10 10 10 8 7 7 7 5 3 3 1
Result      19 10 4  4 4 4 1 1 1 0 0 

#include<cstdio>

using namespace std;

int nlist[1000000];

int main(void) {
	int test_case;
	scanf("%d", &test_case);
	for (int i = 0; i < test_case; i++) {
		int ninput;
		scanf("%d", &ninput);
		for (int j = 0; j < ninput; j++) {
			scanf("%d", &nlist[j]);
		}
		int max = 0;
		long long result = 0;
		for (int j = ninput - 1; j >= 0; j--) {
			if (max < nlist[j])
				max = nlist[j];
			if (max > nlist[j])
				result += max - nlist[j];
		}
		printf("%lld\n", result);
	}
}

아이디어를 떠올리기까지 오래 걸렸지만, 좋은 아이디어를 생각해내서 깔끔하게 풀 수 있었다.

---