백준 1010번: 다리 놓기 (Java, 조합)

☑️ 문제

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

✔️관련 알고리즘 개념

조합

☑️ 문제 분석

• 문제 조건에 N ≤ M 조건에 따라 서쪽 사이트가 동쪽 사이트보다 작거나 같다는 것을 알 수 있다. 최대한 많은 다리를 지으려면 서쪽 사이트는 모두 다리로 연결될 수 밖에 없다. 그렇다면 서쪽 사이트의 개수만큼 동쪽에 있는 사이트를 선택해서 이어 주면 된다.
• 즉, 연산이 최종적으로 MCN이 되는 것이다.
  • 예시 입력1 2C2 = 1
  • 예시 입력2 5C1 = 5
  • 예시 입력3 29C15 = 67863915
• 조합 점화식
  • nCr = nCr-1 + n-1Cr-1 을 사용하여 코드를 작성한다.

☑️ 코드

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

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()); // 테스트 케이스 개수

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

            System.out.println(combination(N, M));
        }
    }

    public static int combination(int N, int M) {
        int[][] p = new int[M+1][M+1];

        for (int i = 0; i <= M; i++) {
            for (int j = 0; j <= i; j++) {
                if(j == 0 || j == i)
                    p[i][j] = 1;
                else p[i][j] = p[i-1][j] + p[i-1][j-1];
            }
        }
        return p[M][N];
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음