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

 

이 문제는 N(2 ≤ N ≤ 1,000,000)이라는 것을 생각하고 풀어야 하는 문제이다.

문제를 해결하려고 가장 첫번째로 생각나는 방법은 아마도 현시점에서 매수를 하고 현재 시점에서 부터 끝까지 탐색해서 그중 최고값을 찾아 이익을 얻는 것일 것이다.

하지만 이방법으로 문제를 풀려고 한다면, 2중 for문이 필요하고 N^2의 시간복잡도를 가지게 된다. 주어진 테스트 케이스를 해결하더라도 N이 커질 경우 시간초과가 발생할 수 있다.

이때, 뒤에서 부터 순회하는 방법을 사용하면 위의 문제를 해결할 수 있다.

뒤에서 부터 순회를 하면서 현시점 (현위치)에서 부터 끝까지 중 최고치를 알아낼 수 있고, 현시점의 매매가 보다 최고 값이 높으면 매수하고 최고치에 팔면 이득을 얻어 낼 수 있다.

설명한 내용을 간단히 정리하면 이렇다

• 최고가 <- 마지막날 값
• 현재 값이 최고가 보다 낮으면
  • 팔아서 이득(최고가 - 현재가)을 남김
• 아니면 ( 현재값이 최고가 보다 크거나 같으면)
  • 최고가 <- 현재가

아래 그림은 1 1 3 1 2 인 경우에 대한 그림이다. 마지막 매수일 부터 매매가와 최고가의 차이를 적었고, 이를 총합 하면 총 이득을 구할 수 있다.