인프런 커뮤니티 질문&답변

안녕하세요. lee님!

해당 문제는 그래프로 해석해서 푸는 것보단, DP로 해석해서 푸는 것이 더 적합하다고 할 수 있습니다.

[DP로 해석해서 푸는 게 더 타당한 이유]

'섹션4의. 실전 문제풀이1' DP 문제인 'BOJ 11726' 강의에서 ‘경우의 수를 구하는 문제이고 경우의 수를 어떤 수로 나눈 나머지를 구하는 형식의 문제라면 DP문제일 확률이 높다’고 언급하였으니 해당 강의를 참고해보시면 좋을 거 같습니다.

[DP 관련 문제를 잘 푸는 법]

DP 문제를 잘 풀려면 문제의 재귀적인 구조를 찾아 DP Table을 적절히 만들 수 있어야 하는데요.

예를 들어, 올려주신 문제에서는 DP Table을 dp[i][j]를 (i, j)까지 도달하는 경우의 수로 정의해보면 문제를 쉽게 접근할 수 있습니다.

정확하게는 보행할 수 없는 경우도 고려해야 하므로 dp[i][j]를 위에서 왔는지 왼쪽에서 왔는지를 고려해주어야 합니다.

따라서 dp[i][j] = {(i- 1, j)에서 (i, j)를 왔을 때의 경우의 수, (i, j - 1)에서 (i, j)를 왔을 때의 경우의 수} 와 같이 dp[i][j]는 2가지 정보를 담게끔 DP Table을 설계해줘야 합니다.

위와 같이 DP Table을 잘 설계하면 쉽게 풀 수 있는 문제입니다.

위 답변이 잘 이해가 안 가신다면, DP 관련 강의인 '섹션3. 필수 알고리즘1'의 DP와 관련된 강의들을 최대한 이해하며 들으시는 것을 추천드립니다.

더불어 여유가 되신다면 '섹션3. 필수 알고리즘1'의 브루트포스 알고리즘 관련 내용도 들으시면 문제를 접근할 때 도움이 많이 될 거 같습니다.

[추가적으로]

추가적으로 문제를 접근할 때 그래프 문제가 아닌 문제를 그래프 문제로 해석하여 접근하는 경우가 빈번하다면 '섹션6. 그래프 알고리즘' 파트를 보시면 그래프는 어떤 문제에 쓰이는지 더 잘 이해하실 수 있을겁니다.

혹여나 DP 파트를 수강한 후에도 올려주신 문제나 DP 문제에 대해 이해가 안 가신다면, 추가 질문 남겨주세요.

또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.

감사합니다. :)