[백준] 1010번 다리 놓기 JAVA (자바) 풀이

문제 1010번 (DP)

 :  도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다

   

 :  다리를 짓기에 적합한 곳 = 사이트

    강 서쪽 사이트 = N개, 동쪽 사이트 = M개 (N ≤ M)

 

 :  한 사이트 - 한 다리 연결 
    크로스처럼 다리끼리 겹칠 수 없다

 

 :  서쪽과 동쪽을 연결하는 다리를 지어라

 

 

 [입력]

 

 : 첫 줄에는 테스트 케이스의 개수 T

 : 그 다음 줄부터 서쪽과 동쪽의 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)

 

 

 [출력]

 : 다리를 지을 수 있는 경우의 수를 출력

 

 

 [과정]

 

 1:1로 연결해야하므로 최대 N개의 다리를 설치할 수 있다

 단, 크로스처럼 다리가 겹쳐서는 안된다

 

 크로스는 동쪽 다리의 인덱스가 순서대로 (이전 인덱스 < 현재 인덱스) 되어야한다고 생각했지만
 다른 코드를 보면 조합 공식을 통해서 푼 것을 볼 수 있다
 조합의 경우 순서를 따지지 않고 동일한 경우의 수를 출력하기 때문에 크로스된 다리는 생각하지 않아도 된다
 즉 크로스된 다리나 크로스되지 않은 다리 모두 조합으로 따지고보면 경우의 수는 같다는 것이다

 

 예)

출처 https://st-lab.tistory.com/194

 

 M의 순서가 3 - 1 - 4 든 1 - 3 - 4 든 조합은 둘다 경우의 수 1로 본다

 

 

 DP로 풀이할 경우

 

 1. i개 중에 i개 선택하지 않을 경우 / 선택할 경우로 나뉜다

• 초기화 하는 식이 다른 문제와 사뭇달라 어려웠다 
• 그냥 외우자! 선택 미선택 둘만 사용!

 2. 조합의 형식으로 보기

• M개중에 N개를 선택하면 된다 
• C(M,N) = dp[M][N]
  
  
• 우리는 무조건 N개만 뽑을 수 있다 (고로 M개는 무조건 N보다는 같거나 크다)
  [ j <= i ]  = [ N <= M ]
  
  
• dp[i-1][j-1]은 현재 지점을 뽑을 경우
  dp[i-1][j]은 현재 지점을 뽑지 않을 경우
  • 예로 N이 3이고 M이 5일 경우
    우리는 5개의 동쪽 지점 중 3개를 택할 수 있다
    dp[5] = dp[4][2] + dp[4][3]
    현재 M 지점을 선택할 경우 위 나머지 4개 지점 중 2개만 선택하거나
    혹 현재 M 지점을 선택하지 않는다면 위 나머지 4개 지점 중 3개 모두 택한다
    이 경우의 수를 모두 더해 출력할 것!!

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int dp[][] = new int[30][30];
        
        for(int i=0; i<30; i++){
            dp[i][0] = 1;
            dp[i][i] = 1;
        }
        
        for(int i=1; i<30; i++){
            for(int j=1; j<=i; j++){
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; 
            }
        }
        while(T-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            
            System.out.println(dp[M][N]);
            
        }
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());  테트스 케이스 반복
    int dp[][] = new int[30][30];  dp 배열 생성
        
 :  for(int i=0; i<30; i++){  입력은 29까지
            dp[i][0] = 1;  선택 안할 경우
            dp[i][i] = 1;  선택할 경우
    }
        
 :  for(int i=1; i<30; i++){
            for(int j=1; j<=i; j++){  N <= M
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];  현 지점 선택할 경우 + 선택하지 않을 경우
            }
    }

 

 :  while(T-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());  서쪽 입력
            int M = Integer.parseInt(st.nextToken());  동쪽 입력
            
            System.out.println(dp[M][N]);  결과 출력
            
    }
  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

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

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *