몰빵

[문제] 어떤 벤처 기업에서 인공지능을 이용한 주식투자 프로그램 <몰빵>을 개발하였다. 우리는 이 투자 프로그램의 성능을 평가하려고 한다. 성능 평가는 몰빵으로 얻은 이득과 이론상으로 가능한 최고 이득과 비교하는 작업이다. 따라서 주식 시세를 미리 안다고 가정했을 때 얻을 수 있는 이득의 최대치를 계산해야 한다.

 

 투자의 기본적인 전략은 낮은 가격일 때 사서 이후 상황을 보다 가장 높아졌을 때 파는 것이다. 표-1에 제시된 12 초 동안의 주식 시세로 설명해보자. 만일 $13인 t=1에 사서 t=6일 때 $15에 팔면 $2의 이득을 얻을 수 있다. 그런데 t=4에서 사서 t=9일 때 팔면 $6의 이득을 얻는다. 단 가장 쌀 때 구입하는 것은 좋은 전략이 아니다. 전체에서 가장 낮은 t=10일 때 $7로 구입했다면 t=12일 때 $9에 팔아 겨우 $2의 이득만 볼 뿐이다. 우리는 시세를 모두 알고 있는 상황에서 언제 사서 언제 파는 것이 가장 좋은지를 계산해야 한다.

 

[입출력] 입력 파일 allin.inp 의 첫 줄에는 전체 주식 가격의 수 N(10,000 <= N <= 500,000)이 주어진다. 이어지는 N개의 각 줄에는 주식 시세 Pt가 정수로 주어진다. 단 1,000 <= Pt <= 10,000 이다.

 여러분은 최고의 이득을 보장하는 구입시점 b(buy)와 판매시점 s(sell)를 찾아서 출력해야 한다. 만일 그러한 시점이 하나 이상이면 b가 더 큰 값, 만일 b가 같으면 더 작은 s값을 선택 한다. 즉 (b,s)로 (10,23), (34,51) 둘 모두가 최적이라면 (34,51)을 정답으로 출력해야 한다. 만일 (10,23), (10,67)이 같은 값은 최고 이득 구간이라면 s가 더 작은 (10,23)을 출력해야 한다. 단 이득 구간은 항상 존재한다.

 

[예제]

allin.inp

12 // N=12

13

15

17

..

7

8

9

allin.out

7 9 // b=7, s=9

 

[풀이]

병합정렬을 하듯이 비교 대상을 최대한 나누고, 왼쪽 부분에서의 최소 값과 오른쪽 부분에서의 최대 값의 차를 계산하여 게속 갱신 시킨다. 갱신 할때마다 왼쪽 값의 인덱스와 오른쪽 값의 인덱스 또한 저장한다. 주의해야 할 점은 최적인 경우가 여러 개 있을때 출력하는 방식이다.

 

https://github.com/sak5010/PNU_Algorithm_2020/blob/master/allin.cpp

sak5010/PNU_Algorithm_2020