11501번 주식

문제 설명

홍준이가 미래의 주식 가격 변동에 대한 정보를 알고 있고, 매일 아래 3가지 행동 중 한 개의 행동만 할 경우, 벌 수 있는 최대 이익을 구하는 문제입니다.

• 주식 하나를 산다
• 원하는 만큼 가지고 있는 주식을 판다
• 아무것도 안한다

 

 

문제 풀이

아이디어

주식을 사는 타이밍

홍준이가 주식 가격 정보를 알고 있으므로, 주식이 오를 때까지는 계속 사고 최고점일 경우에 모두 팔아버리면 최고 이익이 나게 됩니다.

 

최고점 이후

최고점이 지나고 난 뒤에도 고점이 있을 수 있습니다. 그러므로 최고점 이후 날짜들에 대한 주식 최고값을 다시 구해주고, 그 날짜가 되기 전까지 주식을 모두 사면 이익을 가질 수 있게 됩니다.

 

풀이

최고점 찾기의 반복

우선 첫 날부터 마지막 날까지, 최고점이 되는 날을 찾고 첫 날부터 최고점이 되는 날까지 최고 값 - 주식 값을 해서 그 동안 얻은 이익을 구해줍니다.

그 다음, 최고점이 되는 날의 다음 날부터 마지막 날까지, 최고점이 되는 날을 구하고, 이익을 구하는 것을 반복하면 됩니다.

 

 

 

해결

최고점 이후에도 주식을 살 수 있다는 것을 놓쳐 한 번 틀렸었던 문제입니다...

 

문제 링크 : https://www.acmicpc.net/problem/11501

11501번: 주식

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/11501.py