cardbt   1년 전

일단, 기본적으로 계단오르기와 유사하게 작성했습니다.

계단오르기처럼 순서대로 진행해야된다는 규칙이 없긴합니다만, 결과적으로는 동일하다고 생각했습니다.

단, 4, 5, 1, 1, 10, 11 과 같을 경우에는 1은 마시지 않는것이 최대값이 되므로 이걸 응용해서 DP를 작성해봤습니다.


기본적으로는 순서대로 마시되 앞서 마신값의 최대값을 이용하는 방식이고, 세잔을 초과하는 앞 예를 들어 4, 5, 1, 1, 1, 10, 11 이라고해서 1을 모두 넘어갈 필요가 없으므로 최대 세잔 앞에 있는 포도주까지 고려해서 DP를 작성했습니다.


DP로직 자체는 계단오르기와 동일합니다.


예제와 게시판에 올려진 반례를 보두 돌려보고, 이것저것 반례를 돌려봐서 다 맞게 나왔는데, 제출하면 틀렸습니다가 나오네요.

반례가 어떤게 있을까요?

chojl1125   1년 전

3 2 1

계단오르기는 마지막 계단을 반드시 밟아야 하지만 포도주는 마지막 잔을 마시지 않을수도 있다는게 차이겠네요.

cardbt   1년 전

아! 아무 생각없이 마지막 값으로 최대값을 구하고 있었군요...

꼭 마지막일 필요 없다고 알고 있었는데 계단오르기 변형만 생각하다가 무심결에 마지막 값만 보고 있었네요 ㅠㅠ


감사합니다!

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