분류에 다이나믹 프로그래밍이라고 되어 있기는 하지만 그다지 dp가 필요한 문제는 아닙니다.
이것만 생각해 보세요. i-1번째에서 끝나도록 연속하게 고른 경우의 최대 합을 알 때, i번째에서 끝나도록 연속하게 고른 경우의 최대 합은 어떻게 구할 수 있을까요?
1912번 - 연속합
10은 2번째 인덱스에서 끝나는 게 아닙니다. 제가 말한 '끝난다'는 것은 그 수가 포함되면서 끝난다는 뜻입니다. 2번째 인덱스에서 끝나는 경우는 10 -4 와 -4 두 가지가 있고, 이 중 큰 값은 10 -4을 합한 6입니다.
그러면 세 번째 인덱스에서 끝나는 경우는 10 -4 3, -4 3, 3 이렇게 세 가지 경우의 수가 있는데, 이 모두를 고려할 필요가 없다는 게 요점입니다. 우리는 이미 10 -4와 -4 중에 10 -4가 더 크다는 것을 알고 있습니다. 이게 어디에 저장되어 있나요? 바로 두 번째 수까지 포함한 최대 합이 6이라는 사실에 이미 들어 있습니다. 그러면 계산해봐야 할 것은 무엇일까요? 6과 6 3 중 어느 것이 더 큰지만 보면 됩니다.
와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우
뉴메타네요 와 이런 엄청나게 빠른 생각이!
DP라는 건 사실 개념부터가 모호하고 매우 광범위하기 때문에 딱 잘라서 이 문제가 대표적인 DP 문제다 이렇게 말하기는 어렵습니다.
https://www.acmicpc.net/proble... 의 위쪽에 있는 문제들이라면 DP의 기초 문제 정도라고 볼 수 있을 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
snujoon 5년 전
dp라는게 앞의 결과값을 토대로 뒤의 결과값을 진행시켜 나가는거 아닌가요?
방향성에 대한 설명이 필요합니다 ㅠㅠ
dp라는게 정확하게 뭔가요...ㅠㅠ