선생님, dp문제 풀때 말입니다

Question

선생님, 강의 항상 잘 듣고 있습니다. 다이나믹 프로그래밍 문제를 요새 연습하고 있는데  이게 점화식을 적시에 발견해내느냐 그렇지 못하느냐에 따라 쉽게 해결하기도 하고 그렇지 못한 경우도 있네요ㅜㅜ  물론 그래프나 경로 탐색 혹은 메모이제이션을 위해서는 dp가 정말 효율성 면에서 얼마나 중요한지는 알겠습니다만  그 외 다른 dp문제들은 해결을 위한 본질적인 접근이 있을까요?? 질문이 좀 추상적인데  dp문제를 풀다보면 물론 제가 부족해서 놓치는 문제도 있겠습니다만 뭔가 이건 경험이나 실력과 다소 무관한 문제들도  분명히 있다고 여겨져서 여쭤봅니다.. 감사합니다!

김태원 · Answer

안녕하세요^^ 다이나믹을 정복하는 특별한 방법은 없습니다. 문제들이 워낙 다양하고, 독특합니다. 국가대표들도 다이나믹문제만 200개 이상 풀어야 어느정도 카테고리로 분류를 할 수 있습니다. 그 카테고리별 접근방식이 있기는 합니다.  초보들은 문제를 만나면 그게 어느 카테고리인지 잘 모르죠. 결국은 많이 풀어봐야 합니다.  수능수학 4점짜리 킬러문제를 정복하는 방법은 그런 문제를 많이 풀어보는 방법밖에 없는 것처럼 다이나믹도 마친가지 입니다.