Beakjoon 1010 다리 놓기

08 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1010

나의 풀이

서쪽에 있는 i번 사이트와 동쪽에 있는 j번 사이트를 연결할 수 있느 경우의 수를 DP[i][j]라고 해보면 DP[i][j] = DP[i-1][0] + DP[i-1][1] + DP[i-1][2] … + DP[i-1][j-1]이라는 것을 알 수 있다.
예를 들어 N = 4, M = 7 일 때는 아래 그림과 같다. (좌측 상단이 원점이고, 그림에서 회색으로 칠해진 부분은 0을 의미한다.)

먼저 DP[0] 즉 서쪽의 0번 사이트로 연결할 수 있는 경우의 수는 각각 1씩만 가능하고, 4번 사이트 이후에 연결할 경우 서쪽에 있는 나머지 사이트에 다리를 모두 연결 할 수 없기 때문에 경우의 수는 0이 된다.
DP[1][1]에서는 서쪽 1번에서 동쪽 1번으로 연결하기 위해서는 서쪽 0번이 동쪽 0번과 연결하는 경우의 수 하나 밖에 없기 때문에 DP[1][1] = DP[0][0] = 1이 된다.
마찬가지로 DP[1][2]은 서쪽 1번에서 동쪽 2번으로 연결하기 위해서는 서쪽 0번이 0번 또는 1번과 연결해야하기 때문에 DP[1][1] = DP[0][0] + DP[0][1] = 1 + 1 = 2가 된다.
이런식으로 DP[N-1]까지 모든 경우의 수를 구할 수 있다.
최종적으로 DP[N-1]의 모든 값의 합이 다리를 지을 수 있는 경우의 수가 된다.

풀이 코드 : 1010 다리 놓기

#include <iostream>
#include <vector>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    
    int T, N, M;
    cin>>T;
    for(int t=0;t<T;t++){
        cin>>N>>M;
        int DP[30][30] = {0,};
        for(int i=0;i<N;i++){
            for(int j=i;j<M-(N-1-i);j++){
                if(i==0){
                    DP[i][j] = 1;
                }
                else{
                    for(int k=i-1;k<j;k++){
                        DP[i][j] += DP[i-1][k];
                    }
                }
            }
        }
        int answer = 0;
        for(int i=N-1;i<M;i++){
            answer += DP[N-1][i];
        }
        cout<<answer<<"\n";
    }

}

채점결과