[백준/java] 1010번: 다리 놓기 - 조합(Combination), 파스칼의 삼각형

1010번: 다리 놓기

728x90

1010번: 다리 놓기

 

이번 문제는 동적계획법 문제이다.

그냥 정확히 말하면 조합 문제이다.

 

반응형

 

강 동쪽에서 M개 중에 N개를 골라 다리를 연결하는 것이니 조합 문제인 것이 당연할 것이다.

 

Top Down, Bottom Up 둘 중 하나의 방식으로 풀면 된다.

 

하지만, Top Down처럼 재귀로 호출하는 방식은 스택오버플로우를 불러 일으키기 쉬운 문제이다.

 

그래서 Bottom Up 방식으로 문제를 풀면 되는데,

 

이 문제를 푸는 방법중에서는 파스칼의 삼각형을 보면 좋다.

 

1010번: 다리 놓기 -파스칼의 삼각형

이와 같은 삼각형 모습을 이루는 구조가 파스칼의 삼각형인데, 

 

이것은 (x - 1)^2 나 (x-1)^3 을 펼쳐 계산하면 위와 같은 계수로 나오는 것을 알수 있다.

 

파스칼의 삼각형을 적용하여 코드를 구현하면 아래와 같다.

 

package dp;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class PutBridge {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = stoi(br.readLine());
		
		while(T-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int M = stoi(st.nextToken());
			int N = stoi(st.nextToken());
			
			int[] []dp = new int[31][31];
			dp[0][0] = 1;
			
			for (int i = 1; i <= N; i++) {
				for (int j = 0; j <= i; j++) {
					if(j == 0) {
						dp[i][j] = 1;
					} else {
						dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
					}
				}
			}
			
			bw.write(dp[N][M] + "\n");
		}
		
		bw.flush();
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
	
	public static int factorial(int n) {
		if(n == 1) return 1;
		else return n *factorial(n-1);
	}
}