[BAEKJOON] 1010 다리놓기

문제 요약

• 알고리즘 분류: 조합,  동적계획법
• 난이도:  Silver5
• 문제내용:
  • 각케이스마다 서쪽과 동쪽 중복되지않고 연결할수 있는 방법을 출력해라.
• 사이트 주소: https://www.acmicpc.net/problem/1010

11051번: 이항 계수 2

문제풀이

 위 문제는 서쪽과 동쪽을 연결할수 있는 다리를 놓아야 하는데 중복이 되지  않아야 하고 서쪽 지점보다 동쪽 지점이 많아야 한다. 그러므로 조합을 생각해서 풀면된다.

  2가지 푸는 방법이 있다. 하나는 조합공식을 사용해서 푸는 방법과  동적계획법으로 푸는 방식이다.

 

조합 공식 사용 방법

위의 조합 공식으로 사용 하면 된다. 파이썬에서는 factorial 함수를 제공한다.

 

DP로 접근하는 방법

위 사진은 파스칼 삼각형이다. 파스칼 삼각형의 공식은 아래와 같이 정의 할수 있다.

수학 식으로 정리한다면 아래와 같이 정의 할수가 있다.

위 식처럼 (0, 0) ~ (N, P)를 코드로 옮기면 된다.

 

코드

Python

1. DP

for _ in range(int(input())):
    east, west =  map(int, input().split())
    dp = [[1] * (west + 1) for _ in range(west + 1)]
    
    for i in range(2,  west+ 1):
        for j in range(1, i):
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1])
    
    print(dp[west][east])

2. 수학식

from math import factorial

for _ in range(int(input())):
    east, west =  map(int, input().split())
    print(factorial(west) // (factorial(west-east) * factorial(east)))

Java

자바는 factorial 함수 제공하지는 않는다. 귀찮아서 자바는 수학식으로 한 코드는 없다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for(int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			int east = Integer.parseInt(st.nextToken());
			int west = Integer.parseInt(st.nextToken());
			int[][] dp = new int[west + 1][west + 1];
			dp[0][0] = 1;
			for(int i = 1; i <= west; i++) {
				dp[i][0] = 1;
				for(int j = 1; j <= i; j++) {
					dp[i][j] = (dp[i - 1][j] + dp[i - 1][j -1]);
				}
			}
			System.out.println(dp[west][east]);
		}
					
	}
	
}