[JAVA] 백준 1010_다리 놓기

 

[문제링크]

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

 

 

📌 문제 탐색하기

강의 서쪽에는 N개, 동쪽에는 M의 사이트가 위치한다. 서쪽의 모든 사이트를 동쪽의 사이트와 연결해야하는 문제이다. 

서쪽의 사이트 N개와 동쪽의 사이트 M개를 연결하는 조합문제이다. 

 

📌 가능한 시간복잡도 

1. 테스트 케이스 입력 값 처리해야하니까 O(test_case)

2. 효율성을 위해서 DP사용 => DP배열 사용이므로 C(n,r) 한번 계산이니까 이때 시간 복잡도는 O(n,r)인데,

   이때 입력값이 M과 N이니까 O(M,N) ...?

따라서 가능한 시간복잡도는 두가지 경우를 모두 포함한 O(test_case ,M,N) 이라는 결론을 내림.  

 

📌 코드 설계하기

조합을 사용해서 다리를 지을 수 있는 경우의 수를 찾는 문제인데 단순한 재귀를 사용하면 중복으로 인한 시간초과의 문제가 발생 가능하기 때문에 DP를 사용해서 효율적인 풀이를 도전해보았음. 

 

1. scanner 사용해서 각각 N과 M을 입력 받기

2. DP 활용해서 문제 풀이 계획을 가지고 있으니까 DP배열 초기화 선언하고 

3. 점화식 사용해서 계산해야함. return dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r); 계산방식은 구글링..ㅎㅎㅎ

 

📌 정답 코드

import java.util.Scanner;
 
public class Main {
	
	static int[][] dp = new int[30][30];
 
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int T = in.nextInt();
		
		StringBuilder sb = new StringBuilder();
        
		for(int i = 0; i < T; i++) {
			
			// M개중 N개를 뽑는 경우이므로 nCr 에서 n = M, r = N이다.
			int N = in.nextInt();	// N = r
			int M = in.nextInt();	// M = n
						
			sb.append(combi(M, N)).append('\n');
		}
		
		System.out.println(sb);
		
	}
	
	static int combi(int n, int r) {
		
		// 이미 풀린 경우 바로 반환
		if(dp[n][r] > 0) {
			return dp[n][r]; 
		}
		
		// 2번 성질
		if(n == r || r == 0) {
			return dp[n][r] = 1;
		}
		
		// 1번 성질
		return dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
	}
}