백만장자프로젝트

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

SW Expert Academy [D2]

쉬운 문제였지만, 시간 초과가 나서 다시 풀었다.

오답 풀이

i 날에 샀다면, x(>i) 날에 팔아 이득을 챙기면 된다.

여기서 포인트는 max(이득(x)) 를 찾아야 한다는 것이다. 다음의 식을 얻을 수 있다.

sum += max(이득(x)) - 이득(i)

내가 풀이한 코드는, 루프를 두 개 돌리는 것이다. 이렇게 하면, 시간 초과가 발생한다. O(N^2)

정답 풀이

O(N)으로 풀 수 있다.

마지막 날부터 시작해서 1일까지 순차 탐색을 해서, 각 날짜의 최대값을 구하는 것이다.

그리고 이익의 합을 계산한다.