[ 백준 ] 1010번 : 다리놓기 - (C++/C , JAVA/자바 , PYTHON/파이썬 , Node.JS/자바스크립트 )

• 문제

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

1010번: 다리 놓기

---

• 풀이법 ( 알고리즘 )

문제를 보자마자 직감적으로 nCr 공식이 떠올랐다.

m개 중에서 n개를 순서에 상관없이 고르는 것이므로 조합을 사용할 수 있다.

파스칼의 삼각형을 응용하여 풀었다.

---

• 풀이 - C++ ( C )

#include <iostream>

using namespace std;

int T, n, m; // T : 테스트 케이스의 개수 , n : 서쪽 사이트의 개수, m : 동쪽 사이트의 개수
long long dp[31][31]; // dp[x][y] : nCr의 값을 dp[n][r]에 저장

long long solution(int m, int n) {
	if (dp[m][n]) return dp[m][n]; // 이미 값을 구했다면 return
	if (n == m || n == 0) return 1; //서로 같거나 n이 0이라면 return
	
	dp[m][n] = solution(m - 1, n - 1) + solution(m - 1, n); // 파스칼의 삼각형 이론 : nCr = (n - 1)C(r - 1) + (n - 1)Cr
	return dp[m][n]; //위에서 구한 dp[m][n]을 return
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	//input & solve & output

	cin >> T; // 테스트케이스 입력
	while (T--)
	{
		cin >> n >> m;
		cout << solution(m,n) << "\n";
	}

	return 0;
}

• 풀이 - JAVA

import java.util.Scanner;

public class Main {
	static int[][] dp = new int[30][30];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int i = 0; i < t; i++)
		{
			int n = sc.nextInt();
			int m = sc.nextInt();
			
			System.out.println(combi(m,n));
		}
	}
	
	static int combi(int m, int n) {
		if(dp[m][n] > 0) return dp[m][n];
		if(n == m || n == 0) return 1;
		
		dp[m][n] = combi(m-1,n-1) + combi(m-1,n);
		return dp[m][n];
	}
}

• 풀이 - PYTHON

import math
t = int(input())

def combination(n,m):
    return int(math.factorial(m) / (math.factorial(n) * math.factorial(m-n)))

for _ in range(t):
    n , m = map(int, input().split())
    print(combination(n,m))

• 풀이 - Node.js

const fs = require('fs');
const stdin = fs.readFileSync('/dev/stdin').toString().split('\n');

let testNum = stdin[0];

for(let i = 1; i <= testNum; i++)
{
    let str = stdin[i].split(" ");
    let n = parseInt(str[0]);
    let m = parseInt(str[1]);

    let dp = [];
    for (let i = 0; i < m+1; i++) {
        let a = new Array(n+1).fill(0);
        dp.push(a);
    }


    function combi(m,n){
        if(dp[m][n] > 0) return dp[m][n];
        if(n == m || n == 0) return 1;
    
        dp[m][n] = combi(m-1,n-1) + combi(m-1,n);
        return dp[m][n];
    }
    

    console.log(combi(m,n));
}