[C++] 백준 1010 : 다리놓기

다이나믹 프로그래밍

다리가 겹쳐서는 안된다 = 역순이 되어서는 안된다(순서가 있다!)
1 -> 2 (가능) 2 -> 1 (불가능) 무조건 순서가 작은 곳에서 순서가 크거나 같은 곳을 향해야 겹치지 않을 수 있다.
그래서 그냥 조합으로 풀면된다. n개의 다리가 향할 m개의 지점을 찾아주면 된다. 그리고 뽑힌 지점의 순서대로 다리를 배치하면 된다고 보면 된다.

예를 들어 3개의 지점(n)과 10개의 지점(m)이 있다고 한다면 10개 중 3개의 지점을 뽑아보자. 2, 3, 8이 나왔다고 한다면 1 -> 2, 2 -> 3, 3 -> 8 이렇게 다리를 이어주면 무조건 겹쳐지지 않는(다리끼리 가로지르지 않는) 다리를 만들 수 있다.

nCr = n-1Cr-1 + n-1Cr 을 사용해서 쪼개풀 수 있다.
이 식은, DP[n][r] = DP[n-1][r-1] + DP[n-1][r] 로 사용할 수 있다.
결국 파스칼의 삼각형 형태

#include <iostream>
int DP[31][31];

void combination(){
    for(int i = 0; i < 31; i++){
        DP[i][0] = 1;
        DP[i][i] = 1; 
        for(int j = 1; j < i; j++){ // 파스칼의 삼각형 바로 윗줄까지 안다면 구할 수 있다
            DP[i][j] = DP[i-1][j-1] + DP[i-1][j]; // 파스칼의 삼각형 값 채우기
        } 
    }
}

int main(void) {
    int T, N, M;
    scanf("%d", &T);
    combination();
    
    for(int i = 0; i < T; i++){
        scanf("%d %d", &N, &M);
        printf("%d\n", DP[M][N]); // M개중에서 N개 선택 mCn
    }

    return 0;
}

오늘의 키포인트

• 조합 nCr : 서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합이라고 한다.
  

• nCr = n-1Cr-1 + n-1Cr => 파스칼의 삼각형

• 다이나믹 프로그래밍이란? 큰 문제를 작은 조각으로 나누어 푸는 것.

• 아무생각 없이 함수 반환형 int로 쓰지 않기. 반환형 없으면 void 잖아...
  -> 런타임 에러(WithoutReturning) 발생