zeya9643   4년 전

dp 배열의 첫번째 행은 이전 잔도 마시고 이번 잔도 마셨을때

두번째 행은 이전 잔을 마시고 이번 잔을 마시지 않았을때

세번째 행은 이전 잔을 마시지 않고 이번 잔을 마실때로 구분하였습니다

다음 열을 결정할때

이전잔도 마시고 이번 잔도 마셨다면 분명 그 이전의 잔을 마시지 않았을 것입니다 그러므로

전 열의 세번째 행 + 이번 잔의 값의 합이 됩니다

이전 잔을 마시고 이번 잔을 마시지 않았다면 그이전 잔은 마셨을 수도, 마시지 않았을 수도 있습니다 

그러므로 이전 열의 첫번째와 세번째 행의 최댓값이 됩니다.

이전 잔을 마시지 않고 이번 잔을 마신다면 분명 그 이전의 잔을 마셨을 것입니다 (두번 연속 마시지 않는 경우는 고려할 수 없습니다)

그러므로 이전 열의 두번째 행 + 이번 잔의 값의 합이 됩니다 

최댓값은 해당 숫자만큼의 열에서 세 행 중 최댓값이 됩니다

이런 식으로 값을 구했습니다 어떤 부분에 문제가 있는 걸까요?

예제는 제대로 풀 수 있습니다

rhdqor213   4년 전

이런 경우가 있을 수 있으므로 이전 잔과 이번 잔을 모두 마시지 않는 경우도 체크해주셔야 합니다.

skysign   3년 전

앞에 rhdqor213님이 설명하신 부분이 좀더 자세하게 설명되어 있는 영상 첨부합니다.

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