[JAVA]백준 11050번 문제 풀이

# 문제 출제 사이트

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

11050번: 이항 계수 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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        System.out.println(bin(n, k));
    }

    private static int bin(int n, int k) {
        if ( k == 0 || n == k ) return 1;
        else return bin(n -1, k - 1 ) + bin(n - 1, k );
    }
}

• 동적계획법의 사례
• 조합에서 가장 기본이 되는 문제입니다. 일반 점화식을 이용하면 이 문제를 쉽게 해결할 수 있습니다.

N과 K의 값을 입력받고 DP배열을 선언합니다(D[N + 1][N + 1]) 그리고 DP 배열의 값을 다음과 같이 초기화합니다.

 

# DP 배열 초기화

D[i][1] = i // i개 중 1개를 뽑는 경우의 수는 i개

D[i][0] = 1 // i개 중 1개도 선택하지 않는 경우의 수는 1개

D[i][i] = 1  // i개 중 i개를 선택하는 경우의 수는 1개

 

 

# 참고자료

• 유튜브 채널 <하루코딩> => 링크
• 유튜브 채널 <주니온TV 아무거나연구소> => 링크