백준 1010번 - 다리놓기

https://www.acmicpc.net/problem/1010

이 문제를 풀고 난 다음에 해결한 다른 사람들의 소스코드를 보면서 대부분 O(N)으로 해결하는 것을 보았다. 

필자는 DP를 이용하여 O(N^3)으로 접근해 보았다.


사실..O(N)으로 문제를 해결하는 방법이 떠오르지 않았다..
O(N)으로 문제를 해결한 소스코드는 대부분 비슷한 방식으로 풀었는데.. 

정확하게 이해를 하지 못하고 실제로 이 문제를 처음 보았을 때 수학적으로 해결할 방법이 떠오르지 않을 것 같아서 

내가 푼 방식대로 공유하고자 한다.

먼저 점화식은 다음과 같다.

dp[n][m] =서쪽의 정점 n에서 동쪽 정점인 m을 이었을 때의 모든 경우의 수

처음에 문제를 접근했을 때 이중 for문으로
dp[n][m]=dp[n-1][m-1]을 통해서 정답을 구하고자했다.


그러나, 이상한 값이 나와서 한참을 고민하다가 생각하지 못한 경우의 수를 발견하였다.
바로 m-1만 구하는 것이 아니라 m-2와 m-3도 같이 고려해서 더해줘야 올바른 값이 누적되어 저장되는것이다.


예를 들어 dp[3][5]의 경우 이중 for문으로 접근하면 dp[2][4]의 값만 저장된다.
그러나 실제로는 dp[2][3]과 dp[2][2]의 값도 같이 저장해 주어야 dp[3][5]의 값을 올바르게 구할 수 있다. 

이 부분은 마지막 for문에서 k가 n-1부터 m-1까지 더해주는 방식으로 계산하였다.

#include <iostream>
using namespace std;
 
int main(){
    int T,N,M;
    cin>>T;
    
    for(int testCase=0;testCase<T;testCase++){
        scanf("%d %d",&N,&M);
        
        int dp[31][31]={0};
        
        for(int m=1;m<=M;m++)
            dp[1][m]=m;
        
        for(int n=2;n<=N;n++){
            for(int m=1;m<=M;m++){
                for(int k=n-1;k<m;k++)
                    dp[n][m]+=dp[n-1][k];
            }
        }
        
        printf("%d\n",dp[N][M]);
    }
    return 0;
}