kimtaehyun98   4년 전

해당 문제를 그리디로 해결하려 하시는 분이 많을 것 같은데

대부분 

매수 : 다음 날 주식 가격 증가시

매도 : 다음 날 주식 가격 하락시

라는 규칙으로 구현하실 것 같아요. 물론 저도 처음엔 저렇게 구현했습니다..


그럼 아래와 같은 반례가 생깁니다.

다음 날 주식 가격이 하락해도 결과적으론 이득인 경우가 생깁니다.


예를 들어 

2 21 4

101 100

이라고 하면, 분명 다음날 주식 가격이 하락하지만 그럼에도 대출해서 사고, 다음날 하락한 가격에 판매한다 해도 104원이란 cost를 가지게 되고, 

이는 기본금 21원으로 복귀하는 것 보다 더 이득입니다.


이 부분땜에 많이 시간을 투자했네요.. 도움이 되시길 바랍니다..

댓글을 작성하려면 로그인해야 합니다.