와우 드디어 이 문제를 정리해보는거 같다. 시간적인 여유가 조금 부족해서 많이 집중도 못했고 시간이 잡아먹힌게 있었는데 개인적으로 꼭 충분히 이해하고 정리하고 싶은 욕심이 많았던 문제였어서 쭉 해보고 싶었다. 이제는 그래프, 구현 등등 다 해봐야하는데 천천히 좀 시작해야겠다. 사실 개발을 요즘 못하고 있어서 너무 아쉬운건 있다.
하여튼, 이 문제는 이 전에 있었던 일반적인 Stock 문제랑 조금 달랐는데 바로 주식을 팔게되면 Cooldown 이라는 아무것도 못하는 제약이 걸린다는것이다. 그래서 이 문제를 풀려면 어느정도의 포인트를 집는 아이디어가 필요했다.
과연 현재 Stock은 사야하는 주식일까? Cooldown 에 있어야 하는 주식일까?
이 두 결정권에 대한 해답을 가졌다면 DP 배열에 해당 index에 최대 profit을 저장해주면 된다.
그렇지만 사야하는것과 Cooldown의 시나리오를 잘 살펴보자. 당장 내가 주식을 사게된다면 만들 수 있는 Profit은 없다 왜냐면 Profit은 팔아야 나오는 이득이기 때문에! 그리고 Cooldown 상황에서는 아무것도 못하기 때문에 Profit을 만들 수 없다.
그렇다면 위에 두 상황일 경우 현재 만들 수 있는 가장 큰 Profit은 DP[i-1]. 그렇다 바로 전날 Profit이다. 왜냐면 전날에는 무슨 짓을 했든 어쨌든 최대 Profit이 정해져있기 때문이다.
그런데 여기서 어려운 결정은, 현재 Stock이 팔아야하는 주식이면 어떻게 될까? 이다.
내가 지금 주식을 팔아야 하는거면 나는 당연히 이 전에 있었던 모든 주식 중에 가장 싼 값에 주식을 찾고 팔아야한다. 여기에다가 추가적으로 지금까지 누적된 최고 Profit까지 더해야지 현재 Stock에서 얻을 수 있는 최고 Profit을 얻는다. 식으로 만들면,
현재의 가장 높은 Profit =
지금까지 누적된 Profit + 현재 Stock - 이전에 있었던 가장 값싼 Stock
가장 값싼 Stock을 구하기 위해서 한번 더 for 룹을 돌리면은 시간이 망한다. 그렇다면 위에 식을 살짝 다르게 바꿔야한다.
(지금까지 누적된 Profit - 이전에 있었던 가장 싼 Stock) + 현재 Stock
왜냐면은 현재 Stock은 변하지 않는 값이기 떄문이다.
그렇다면 누적된 Profit은 어느 구간일까? 그 구간은 바로 현재 i의 2단계 전인 i-2이다. 왜냐면 i-2 에서 Sell 을 해야지 무슨 짓을 해도 가장 큰 Profit이 만들어진 구간이기 때문이다.
그렇게 위에 가로친 식을 Max_diff 라는 식 안에 넣어주면은 답을 풀 수 있다. 솔직히 이해하기 힘든 문제라 계속해서 노트에 적고 생각해줘야한다 끝!
class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 1) return 0;
int[] dp = new int[prices.length];
dp[0] = 0;
dp[1] = Math.max(prices[1] - prices[0], 0);
int max_diff = Math.max(-prices[0],-prices[1]);
for(int i = 2; i < prices.length; i++){
dp[i] = Math.max(dp[i-1], prices[i] + max_diff);
max_diff = Math.max(max_diff, dp[i-2] - prices[i]);
}
return dp[prices.length-1];
}
}