[JAVA]백준 1010번: 다리 놓기

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

1010번: 다리 놓기

 

 

 

문제만 이해하면 해결방법은 단순한 조합문제로 아주 쉬운 문제이다.

 

조합의 식을 nCr 이라고 할 때,

강 동쪽을 n 

강 서쪽을 r로 생각하면 된다.

 

동쪽에서 r개의 사이트를 고르는 경우의 수(순서가 없고 중복도 없다.)

 

r개의 조합을 고르면,  서쪽 사이트와 순서대로 선을 그으면 되기 때문에 겹칠 일이 없다.

 

따라서, 우리는 

 

    0< N, M<30

 

위의 조건만 고려해주면 된다.

 

저 조건으로 DFS는 절대 시간초과가 난다.

 

그래서 조합 공식에 DP를 적용하여 푼다.

 

 

 

위의 조합 공식으로 

for(int i=2;i<30;i++) {
  for(int j=1;j<30;j++) {
  	dp[i][j] =dp[i-1][j]+dp[i-1][j-1]; 
  }
}

 

최대 가능한 [30][30] 2차원 배열을 만들어

조합의 결과를 계산하여 저장한다.

 

그리고 결과는 입력받은 N과 M 위치의 dp값을 출력( System.out.println(dp[M][N]); )해주는 방법으로 풀었다.

 

 

 

[JAVA] 전체 코드

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

public class Main {
	
	static int t, N, M, count;
	// dp 배열 :(문제 조건) N,M이 최대 30
	static int[][] dp = new int[30][30];
	public static void main(String[] args) throws NumberFormatException, IOException {

		/*  
        		Idea : 조합을 만드는 문제 
			조건 : 숫자가 0<= n,r<=30 (시간과 효율 고려) + dp 배열[]			
		*/
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for(int T=0 ; T<t;T++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			count = 0;
			
			N = Math.min(N,(M-N));

		
			for(int i=0;i<30;i++) {
				dp[i][i] = 1;
				dp[i][0] = 1;
			}
			
			
			// 반복문 사용
			// 반복문을 사용하는 초기 작업은 2C1이어야 함
			// 2C1 = 1C1 + 1C0 
			
			for(int i=2;i<30;i++) {
				for(int j=1;j<30;j++) {
					dp[i][j] =dp[i-1][j]+dp[i-1][j-1]; 
					
				}
			}
			
			
			
			//com(M,N);
			// M-N+1 번  
			System.out.println(dp[M][N]);
			
		}
				
		
	}

}