dbehxks02   2년 전

이중 반복문으로 0,0부터 n-1,n-1까지 차례대로 살피면서 왼쪽과 오른쪽에서 내가 어떤 우유맛을 먹었는지 확인하고 

확인한 것을 기반으로 왼쪽 값과 오른쪽 값을 비교해서 더 큰 값을 dp에 저장을 했습니다. 근데 의아했던 부분이 있습니다.

예를 들어 (코드 10번 라인) 왼쪽과 위에서 먹었던 우유는 서로 다른 맛이었고 현재 좌표 dp에 어떤 맛을 저장하냐에 따라서 차후에 값이 크게 바뀔지도 모르는데  여기서 무작정 더 큰 값을 넣으면 안 되지 않나요??

pichulia   2년 전

이 문제의 경우, dp에 저장된 값이 곧 다음에 선택될 때 사용될 값이라는 특성이 있습니다.

내가 1 까지 마신 상태일 때, 지금 있는 2 를 선택한 대신, 과거에 선택했던 1 을 계속 keep 해둔 경우를 생각해봅시다. 이렇게 아껴놓은 1 을 써서 미래에 2 를 먹는다고 해도, 지금 있는 2 를 선택하는 것이랑 차이가 없습니다. 오히려 미래에 있을 수 있던 0 을 놓치는 계기가 됩니다.

따라서 이 문제에 한해선 지금처럼 최대값만 저장해도 정답입니다.

dbehxks02   2년 전

답변 감사합니다(_ _) 제가 궁금했던 부분을 정확히 짚어주셨는데 한 가지 더 여쭙고 싶은 것이 있습니다!

답변 해주신 것을 생각해봤을 때 오히려 0을 놓치는 계기가 될 수도 있다 하셨는데 오히려 더 많이 먹을 수 있는 계기가 될 수도 있는데 

이런 테스트 케이스는 이 문제에서 존재하지 않는 것인가요?, 아니면 이런 생각을 이 문제에 한해서는 안 해도 된다는 것인가요?

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