[백준_1010번] 다리 놓기

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

1010번: 다리 놓기

[문제]

 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

 

 

[입력 조건]

 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

 

[코드]

import java.util.*;
/*
 * <조합공식 성질>
 * n+1Cr+1 = nCr + nCr+1
 * nC0 = nCn = 1
 *
 * <알고리즘>
 * 서로 다를 n개에서 r개를 뽑는 nCr 조합공식을 사용하여 푸는 문제이다.
 * 조합은 순서를 고려하지 않는다. 조합을 사용하면 다리가 교차하는 것을 신경쓰지 않아도 된다.
 * 예를 들어 (1,2,3,4,5)에서 (3,1,4)을 뽑았다고 하면 다리가 교차되지 않는(1,3,4)와 같은 경우이다.
 */
public class BaekJoon_1010 {
	public static int[][] dp=new int[30][30];
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int testcase=sc.nextInt();
		StringBuilder sb=new StringBuilder();
		
		while(testcase-->0) {
			int r=sc.nextInt();
			int n=sc.nextInt();
			
			sb.append(bridge(n,r)).append('\n');
		}
		System.out.println(sb);
	}
	
	public static int bridge(int n, int r) {
		if(dp[n][r]>0)
			return dp[n][r];
		
		// 조합공식 : nC0 = nCn = 1
		if(r==0||n==r)
			return dp[n][r]=1;
		
		// 조합공식 중 n+1Cr+1 = nCr + nCr+1에 n-1을 대입한 식
		return dp[n][r]=bridge(n-1,r-1)+bridge(n-1,r);
	}
}

 

[고찰]

 이번 문제의 2가지 중점은 다리를 교차 없이 어떻게 선택할 것인가, 시간초과 없이 코드를 어떻게 짤것인가 이다. 우선 다리를 교차 없이 선택하는 방법은 조합공식인 nCr을 사용하는 것이다. 그리고 시간초과 없이 프로그램을 구성하기 위해서는 동적 계획법을 사용하는 것이다. 이때는 조합공식 두 개를 사용하야 하는데 이러한 부분은 다른 문제에서도 사용될 수 있기 때문에 계속 기억해둬야 할 것 같다.

<조합공식 성질> ① n+1Cr+1 = nCr + nCr+1 ② nC0 = nCn = 1