[백준] 조합론_2

서론

---

조합론 문제풀이_2

---

11050 : 이항 계수 1

---

문제

---

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

11050번: 이항 계수 1

---

해설

---

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

public class Main {

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        res = new int[N+1][K+1];

        sb.append(dynamic(N, K));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static int dynamic(int N, int K){
    	//배열 값이 0보다 크면, 이미 구한 적 있는 값이므로 이를 사용
        if(res[N][K] > 0){
            return res[N][K];
        }
		//nCn, nC0 인경우 = 1
        if (N == K || K == 0) {
            res[N][K] = 1;
            return res[N][K];
        }
        //nCr = (n-1)C(k-1) + (n-1)C(k)공식이용
        res[N][K] = dynamic(N-1, K-1) + dynamic(N-1, K);
        return res[N][K];
    }
}

 

 

이 문제는 이항 계수를 구하는 문제로, 이항 계수란, (a+b)^n 의 식에서 계수를 의미한다.

따라서, 문제에서 제공하는 예시 5,2를 식으로 나타내면, 아래와 같다.

여기서 5C2 = 10이므로 결과가 10이 나오는 것이다 (a^3*b^2)의 계수

이를 구하기 위해서 파스칼의 삼각형을 사용할 수 있다.

---

https://namu.wiki/w/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98%20%EC%82%BC%EA%B0%81%ED%98%95

https://namu.wiki/w/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98%20%EC%82%BC%EA%B0%81%ED%98%95

해당 공식을 아래 그림을 통해 눈으로 직접확인할 수 있다.

---

1010 : 다리 놓기

---

문제

---

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

1010번: 다리 놓기

---

해설

---

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

public class Main {

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

        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());
            res = new int[M+1][N+1];

            sb.append(dynamic(M, N)).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }

    public static int dynamic(int N, int K){
        if(res[N][K] > 0){
            return res[N][K];
        }

        if (N == K || K == 0) {
            res[N][K] = 1;
            return res[N][K];
        }
        res[N][K] = dynamic(N-1, K-1) + dynamic(N-1, K);
        return res[N][K];
    }
}

이 문제도 위의 방법도 동일한 알고리즘을 이용하였다.

해당 문제는 겹치지 않게 다리를 놓는 문제이며, 강 동쪽의 M개의 포인트 중, 강 서쪽의 N개와 겹치지 않게 연결하면 되는 문제이다.

즉, M개의 포인트 중 N개를 중복없이 선택하면 되는 문제이다.

---

결론

---

이항계수가 정확히 뭐였고 어떤 공식이 있었는지 기억이 안나서 찾아본건 비밀..ㅎ

---