snujoon   5년 전

dp라는게 앞의 결과값을 토대로 뒤의 결과값을 진행시켜 나가는거 아닌가요?

방향성에 대한 설명이 필요합니다 ㅠㅠ 

dp라는게 정확하게 뭔가요...ㅠㅠ

djm03178   5년 전

분류에 다이나믹 프로그래밍이라고 되어 있기는 하지만 그다지 dp가 필요한 문제는 아닙니다.

이것만 생각해 보세요. i-1번째에서 끝나도록 연속하게 고른 경우의 최대 합을 알 때, i번째에서 끝나도록 연속하게 고른 경우의 최대 합은 어떻게 구할 수 있을까요?

snujoon   5년 전

10 -4 3 1 5 6 -35 12 21 -1

여기서 최대값을 비교하려고하면...

2번째 인덱스에서 끝난다고하면

10과 10-4를 비교하고

3번째 인덱스에서 끝난다고 한다면

10 -4 + 3

-4 + 3

3

을 비교해야하는거 아닌가요??

인덱스 i에서 끝난다고 할때 거기에 +일지 -일지 알 수 없으니 모든걸 비교해야하는게 아닌가요?

djm03178   5년 전

10은 2번째 인덱스에서 끝나는 게 아닙니다. 제가 말한 '끝난다'는 것은 그 수가 포함되면서 끝난다는 뜻입니다. 2번째 인덱스에서 끝나는 경우는 10 -4 와 -4 두 가지가 있고, 이 중 큰 값은 10 -4을 합한 6입니다.

그러면 세 번째 인덱스에서 끝나는 경우는 10 -4 3, -4 3, 3 이렇게 세 가지 경우의 수가 있는데, 이 모두를 고려할 필요가 없다는 게 요점입니다. 우리는 이미 10 -4와 -4 중에 10 -4가 더 크다는 것을 알고 있습니다. 이게 어디에 저장되어 있나요? 바로 두 번째 수까지 포함한 최대 합이 6이라는 사실에 이미 들어 있습니다. 그러면 계산해봐야 할 것은 무엇일까요? 6과 6 3 중 어느 것이 더 큰지만 보면 됩니다.

snujoon   5년 전

와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 와우 

뉴메타네요 와 이런 엄청나게 빠른 생각이! 

snujoon   5년 전

그렇다면

djm03178   5년 전

그렇게 되겠네요.

snujoon   5년 전

djm03178님 사랑합니다 >< 메번 도와주시고 덕분에 통과했습니다

snujoon   5년 전

djm님 하나만 더 질문드릴게요 dp를 제대로 공부하고 싶은데 백준에서 '이게 dp다' 라고 할만한 문제좀 추천해주실 수 있나요??

djm03178   5년 전

DP라는 건 사실 개념부터가 모호하고 매우 광범위하기 때문에 딱 잘라서 이 문제가 대표적인 DP 문제다 이렇게 말하기는 어렵습니다.

https://www.acmicpc.net/proble... 의 위쪽에 있는 문제들이라면 DP의 기초 문제 정도라고 볼 수 있을 것 같습니다.

snujoon   5년 전

결국 여러번 해보면서 흐름을 체득하는게 방법이겠네요 개념자체가 모호하다면 열심히 하겠습니다! 질문 자꾸드려서 죄송했습니다 ㅠ

persona_k   4년 전

대박 저도 영감 얻고 갑니다!.

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