백준 1010 다리 놓기

문제

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

풀이전략

1. 나는 접근하지못하였지만.... 단순한 아이디어가 있다.
   
   이렇게 왼쪽에 2개 오른쪽에 4개가 있을 때
   dp[2][4] = dp[1][3] + dp[1][2] + dp[1][1] 이라는 규칙을 찾을 수 있다.
   이를 활용하여 순차적으로 계산하면 된다.

코드

#include<bits/stdc++.h>

using namespace std;

#define mine


int main(){
    ios_base::sync_with_stdio(false);
    freopen("../input.txt","rt",stdin);
    
    int T, N, M, i, j, k;
    long long dp[31][31];
    memset(dp, 0, sizeof(dp));

    // 1개 뽑을때 i개 있을때 경우의 수들
    for(i=1; i<31; i++) dp[1][i] = i;

    for(i=2; i<31; i++){
        for(j=i; j<31; j++){
            for(k = j-1; k>=i-1; k--) dp[i][j] += dp[i-1][k];
        }
    }
    

    return 0;
}

소감

나는 접근하지 못하여 다른분들의 코드를 보았지만, 충분히 해결할 수 있는 부분이다... 처음에 초기화하는 부분을 잊지 말고, 이러한 아이디어를 제대로 익혀야겠다.