[platinum5] [풀이,분류 안봄]1231 주식왕 동호

https://www.acmicpc.net/problem/1231

 

처음엔 재밌을 뻔했으나, 디버깅으로 재미없어진 배낭 문제 였다.

아이디어는 생각보다 간단하다. 

주식을 얼마나 가지고 있느냐는 생각하지 말고, 현재 가지고 있는 주식을 포함한 총 자산을 중심으로 생각하면 된다.

 

즉 Day2에 자산 100, 주식1 , 주식2 를 가지고 있다면 그건 자산 126 인 것이다. 주식은 언제나 사고 팔고가 가능하니 가능한 발상이다.

 

그렇다면 현재 자산에서 주식을 어떻게 사면 다음날 자산이 최대가 될 수 있을 까 생각하면 된다. 

주식1 ~N 개중 적절하게 고른다면, (다음날 가격 - 오늘 가격)의 최댓값을 알 수 있을 것이다. 이것은 바로 배낭문제로 풀수 있다.

knapsack[오늘 산 가격 총합] = 내일 - 오늘 시세 차익의 최댓값    으로 생각하면 된다.

 

 

이렇게 문제는 금방 풀었지만, 디버깅은 1시간 20분이나 걸렸다...  나는 당연히 주식은 하루에 하나만 살 수 있을 것이라고 생각하고, knapsack에서 중복을 막기 위해     for( 가격총합 >= 0 가격총합 --) 으로 줄여가며 풀었던 것이다..

질문게시판을 보고나서야 중복이 가능하다는 걸 알고, 역순에서 오름차순 으로 바꿔 AC를 받았다. 참 허탈하다..