ddolgu14   9달 전

안녕하세요. 백준카페 뉴비입니다. 

다름이 아니라 dp  를 공부하는데 어려움이 많습니다. 도움이 필요합니다 여러분들~

2342, ddr문제를 어떻게 풀어야할지 잘 모르겠습니다. 힌트 한 개만 던져주십쇼ㅠㅠ

chatterboy   9달 전

T[i][j][k] = i번째 지시사항까지 고려하고, 왼쪽 발과 오른쪽 발이 (j,k)에 있을 때 최소의 힘

이라고 정의를 하고 풀었습니다~

ddolgu14   9달 전

정말 감사합니다!!

flflds0811   9달 전

dp문제는 대부분 dp테이블은 어떠한 상태를 나타낼 수 있도록 정의하고

들어있는 값은 그 상황에서 구하고자하는 값으로 정의하시면 됩니다.

최적값이면 그 상태에 도달하는 최적값or 그 상태부터 나아가는데 최적값

경우의 수이면 그 상태에 도달하는 경우의 수or 그 상태로부터 나아갈 수 있는 경우의 수

상태를 나타내는 방법에는 보통 어떤 순서에 어떠한 상태로 왔냐 로 정의하시면 편합니다.

이 문제에서는 위에 분이 답변한 바와 같이 x번째 순서에 발의 상태(왼발과 오른발)로 나타내면 되기때문에

3차원으로 나타내게 됩니다. 이 때 dp테이블이 저장될 값은 최소의 힘을 구하는 문제이기 때문에

이 문제에서는 dp테이블을 x상태까지 해당 발위치로 왔을 때의 최소 힘  or

x상태에서 해당 발위치에 있을 때 남은 부분을 완료할 때 최소 힘 으로 정의하여

top-down방식이나 bottom-up방식으로 문제를해결할 수 있습니다.

ddolgu14   9달 전

도움 정말 감사합니다~!!

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