[백준] CLASS2 11050 이항 계수 1 - JAVA [자바]

 안녕하세요. 이번에는 백준 11050 이항 계수 1 문제를 풀어보려고 합니다.

 

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

11050번: 이항 계수 1

---

Problem

사진 1. 문제

---

Solution

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

public class Main {
 
	static int[][] dp;
 
	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());
 
		dp = new int[N + 1][K + 1];
 
		System.out.println(BC(N, K));
	}
 
	static int BC(int n, int k) {
		if(dp[n][k] > 0) {
			return dp[n][k];
		}
 
		if(k == 0 || n == k) {
            return dp[n][k] = 1;
		}

		return dp[n][k] = BC(n - 1, k - 1) + BC(n - 1, k);
	}
}

 이번 문제는 이항 계수를 구하는 문제이다. 이항 계수를 잘 몰라서 위키 백과를 먼저 참고하여 문제를 풀 수 있었다. 

 

이항 계수란, 

사진 2. 이항 계수 정의

 

 

 

 이렇게 이항 계수를 풀려고 보면 파스칼의 삼각형을 보고 접근 법을 배울 수 있다. 왼쪽의 파스칼의 삼각형을 보고 점화식을 세우면 맨 앞과 맨 뒤는 1이 들어가는 것 과 가운데 숫자는 중간 값들의 합으로 나타나는 것을 확인할 수 있다

 

 

 

 

 조건 1. 양쪽 끝은 1이 들어간다.

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

 

 조건 2. 가운데 숫자는 중간 값들의 합이다.

dp[n][k] = BC(n - 1, k - 1) + BC(n - 1, k);

 이렇게 2가지의 조건들을 구하면서 이항 계수를 풀어 나가면 된다.

---

Performance

사진 2. 실행 결과

---

Reference

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98