[알고리즘][동적 계획법] 다리 놓기(백준)

다이나믹 프로그래밍 (동적 계획법) 알고리즘 문제 - 다리 놓기 (백준)

점화식을 찾는 과정이 상당히 어려웠다.

N의 수를 차례로 늘려보기도 하고, M의 수를 차례로 늘려보기도 했으나

도저히 감이 잡히지 않아 굉장히 어려운 문제였다.

하지만 다리가 크로스 될 수 없다는 조건을 떠올려서 간신히 점화식을 구할 수 있었다.

N의 가장 위에 점이 M의 가장 위의 점에다 다리를 놓게 된다면

dp[N-1][M-1]의 경우의 수를 얻을 수 있다.

거기에다 M에 하나의 점이 추가되기 전인 dp[N][M-1]의 경우의 수를 더해주면 점화식을 완성할 수 있다.

(N과 M은 1부터 차례대로 올라가면서 모든 경우의 수를 찾아 dp에 저장하였다.)

dp[N][M] = dp[N-1][M-1] + dp[N][M-1]

설명이 상당히 미흡한 부분이 많은데, 이해가 가지 않는 다면

기존에 구해 놓은 답을 통해 현재의 답을 찾는다 라는 동적 계획법의 기본 원리를 떠올려보고

몇 가지의 케이스를 노트에다 적으면서 점화식을 찾아내는 것도 좋은 방법일 것이다.

동적 계획법 문제 - 다리 놓기 (백준)

항상 느끼는 것이지만 수행 시간이 다른 사람보다 많이 나오는 것 같다.

시간 단축을 위해 dp[0][M]을 초기화하는 과정을 빼고 싶었으나 GG..

다이나믹 프로그래밍은 정말 많이 풀어봐야겠다는 생각이 든다..