[JAVA] 다리 놓기

NoHae·2025년 3월 31일

백준

목록 보기

30/106

문제 출처

단계별로 풀어보기 > 조합론 > 다리 놓기
https://www.acmicpc.net/problem/1010

문제 설명

강서에는 다리를 지을 수 있는 사이트가 N개,
강동에는 다리를 지을 수 있는 사이트가 M개 일 때,
강서와 강동을 이을 수 있는 다리를 지으려고 한다.
이 때, 다리는 서로 겹쳐질 수 없을 때, 다리를 지을 수 있는 경우의 수를 구하라.

접근 방법

파스칼의 삼각형을 이용하여 경우를 2가지 만들어서 dp배열을 생성한다.

1번 경우) nCn, nC1 의 값은 1이다.
이를 이용하여 반복문을 통해 dp[i][0], dp[i][i]에 1로 초기화 한다.

2번 경우 ) nCr = n-1Cr-1 + n-1Cr 이다.
이를 이용하여 강동의 다리를 설치할 수 있는 곳 n이 2인 경우 부터 30까지, 강서의 다리를 설치할 수 있는 곳 r이 1인 경우부터 30까지 이중 반복문을 이용한다.(강동 다리가 1개인 경우는 어쩔 수 없이 1이기 때문)

import java.io.*;
import java.util.StringTokenizer;

public class 다리_놓기 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        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 k =2; k<30; k++){
            for(int j =1; j<30; j++){
                dp[k][j] = dp[k-1][j-1] + dp[k-1][j];
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i =0; i<T; i++){
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());

            sb.append(dp[N][M]).append("\n");

        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }
}

Review

import java.io.*;
import java.util.StringTokenizer;

public class 다리_놓기_review {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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 j = 2; j<30; j++){
            for(int k = 1; k<30; k++){
                dp[j][k] = dp[j-1][k-1] + dp[j-1][k];
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int l = 0; l<T; l++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            sb.append(dp[M][N]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
        

    }
}