24885번 - 주식
해당 문제를 그리디로 해결하려 하시는 분이 많을 것 같은데
대부분
매수 : 다음 날 주식 가격 증가시
매도 : 다음 날 주식 가격 하락시
라는 규칙으로 구현하실 것 같아요. 물론 저도 처음엔 저렇게 구현했습니다..
그럼 아래와 같은 반례가 생깁니다.
다음 날 주식 가격이 하락해도 결과적으론 이득인 경우가 생깁니다.
예를 들어
2 21 4
101 100
이라고 하면, 분명 다음날 주식 가격이 하락하지만 그럼에도 대출해서 사고, 다음날 하락한 가격에 판매한다 해도 104원이란 cost를 가지게 되고,
이는 기본금 21원으로 복귀하는 것 보다 더 이득입니다.
이 부분땜에 많이 시간을 투자했네요.. 도움이 되시길 바랍니다..
댓글을 작성하려면 로그인해야 합니다.
kimtaehyun98 4년 전 2
해당 문제를 그리디로 해결하려 하시는 분이 많을 것 같은데
대부분
매수 : 다음 날 주식 가격 증가시
매도 : 다음 날 주식 가격 하락시
라는 규칙으로 구현하실 것 같아요. 물론 저도 처음엔 저렇게 구현했습니다..
그럼 아래와 같은 반례가 생깁니다.
다음 날 주식 가격이 하락해도 결과적으론 이득인 경우가 생깁니다.
예를 들어
2 21 4
101 100
이라고 하면, 분명 다음날 주식 가격이 하락하지만 그럼에도 대출해서 사고, 다음날 하락한 가격에 판매한다 해도 104원이란 cost를 가지게 되고,
이는 기본금 21원으로 복귀하는 것 보다 더 이득입니다.
이 부분땜에 많이 시간을 투자했네요.. 도움이 되시길 바랍니다..