동적계획법 위키를 참고하셔서 다양한 문제들을 다루어보는 게 중요하다고 생각합니다.

제가 잘하는건 아니지만 @hongjun7 님께서 말씀하신 것처럼 많은 문제를 접해보는 것이 중요하다고 생각합니다.

문제를 많이 풀어야하는 군요..

저도 옛날에는 동적계획법으로 풀릴 것 같다는 느낌은 드는데, 점화식 정의가 잘 안 떠오르는 경우가 많았어요.

그런데 그냥 문제를 자꾸 접하고 풀다보니까 경험적(?)으로나 직감적(?)으로 떠오르는 경우가 많더군요.

마치 우리가 삼각형 모양으로 *를 출력할 때 아무 생각없이 이중 for문을 쓰듯이...

아, 물론 그냥 조건식을 전개하다가 '이걸 최적화시키면 되는데 이런이런 요소가 필요하니까 이런 점화식을 세울 수 있겠군'하는 경우도 있어요ㅋㅋ

같은 동적계획법이라도 문제를 푸시다보면 시간복잡도를 줄이기 위해서 그 문제만이 가지고 있는 고유한 특성들을 사용하게 되는데, 보통 수학적으로 전개되더라구요.

그리고 생각하다가 문제에서 요구한 건 아니지만, 번뜩이는 아이디어 같은 것들도 항상 메모해두면 좋다는 생각을 했습니다.

그리고 질문할 때, "~까지는 생각했는데 ~하는 부분에서 어렵습니다. 어떻게 할 수 있을까요?"라는 식으로 질문을 하면 잘하는 분들이 많은 도움을 주실 거에요.

네 감사합니다. ^.^ 도움이 많이 됬어요.