[백준] 1010번: 다리놓기 풀이 및 해설(C++)

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

1010번: 다리 놓기

 

풀이

강 서쪽에는 N개의 다리가 강 동쪽에는 M개의 다리가 있다. 다리는 최대로 지어야 한다. 그런데 N<=M이므로

다리는 항상 N개 지어진다. 그렇다면 동쪽의 M개 다리 중 N개 다리를 고른다. 그리고 동쪽의 다리를 위에서 부터 차례로 서쪽에 있는 다리를 위부터 대응시키면 된다.

 

즉, M개 중에서 N개를 고르는 경우의 수, M Combination N이다.

이는 M!/(M-N)!*N! 과 같다.

 

하지만 일일이 팩토리얼을 계산하면 시간초과가 날 수 있다.

여기서는 콤비네이션의 공식을 이용해 동적으로 계산하자!

nCr= nC(r-1) +(n-1)C(r-1) 과 같다.

 

즉 n과 c를 각각 2차원 배열로 표현했을때 

dp[n][r]= dp[n][r-1] +dp[n-1][r-1] 과 같은 것이다.

동적계획법을 이용해 아래서부터 값을 차근차근 구해나가면 된다.

 

 

해답 코드

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main()
{
    fastio;
    int dp[31][31]={0};//0으로 2차원 배열 초기화
    unsigned int n,m,count;//정수범위 초과를 막기 위해 unsigned int로 선언
    cin>>count;//몇개의 답을 출력해야 하는지 count에 저장
    for(int k=0;k<count;k++){
    	cin>>n>>m;
    	for(int i=1;i<m+1;i++){
        	dp[i][1]=i; //i개 중 1개를 고르면 경우의 수는 i
        	dp[i][i]=1; //i개 중 i개를 고르면 경우의 수는 1
        	dp[i][0]=1; //i개 중 0개를 고르면 경우의 수는 1
            //동적계획법의 기반이 되는 베이스 값들을 미리 반복문으로 출력하는 것이다.
    	}
   		for(int i=2;i<m+1;i++){
    		for(int j=1;j<n+1;j++){
    			dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                //문제에서 요청한 값이 나올 때 까지 이전의 값들을 채워가며 동적 계획법을 작동시킨다.  
    		}
    	}
    	cout<<dp[m][n]<<'\n';//답 출력
    }
    return 0;
}

 

 

PLUS

결국 핵심은 위 문제 콤비네이션 문제임을 깨닫고, 콤비네이션 공식으로 동적계획법을 적용하는 것이다.