2022.03.17 82일차

백준 11050번 (이항 계수 1)

문제

자연수 (N)과 정수 (K)가 주어졌을 때 이항 계수
(N K)를 구하는 프로그램을 작성하시오.

나의 풀이

1. N개 중 K를 선택
2. 조합 활용하기

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

public class Main {
    static int[][] arr;

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

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


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

        System.out.println(func1(N, K));
    }

    static int func1(int n, int k) {

        if (arr[n][k] > 0) {
            return arr[n][k];
        }

        if (k == 0 || n == k) {
            return arr[n][k] = 1;
        }

        return arr[n][k] = func1(n - 1, k - 1) + func1(n - 1, k);
    }
}

생각하기

• nCr 공식 정리, 파스칼의 삼각형, 파스칼의 법칙

• 어떤 수가 n개 있을 때 이들 중 r개를 뽑는 경우 -> 조합 공식

• n! / r!(n - r!)

• 파스칼의 법칙
  

• n과 r이 같거나 r이 0이면 1
  

• 동적계획법 공부하기