[BOJ 백준] 이항 계수 2(11051) C++, Java

 

링크 : https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

문제 설명 : 

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

 

입력 : 

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000 , 0 ≤ K ≤ N)

출력 : 

N C K를 10,007로 나눈 나머지를 출력한다

 

예제 입력 : 

5 2 

예제 출력 : 

10

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

Java 코드 : 

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

// 이항계수1 11050
public class Main {

	static int N, K;

	static int[][] combination;

	static final int MOD_NUMBER = 10_007;

	public static void main(String[] args) throws IOException {
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		st = new StringTokenizer(br.readLine());

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

		// 2. 파스칼의 삼각형 통한 조합 구하기
		combination = new int[N + 1][N + 1];

		combination[0][0] = combination[1][0] = combination[1][1] = combination[1][1] = 1;

		// 파스칼의 삼각형
		for (int i = 2; i <= N; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0 || j == i) {
					combination[i][j] = 1;
				} else {
					combination[i][j] = (combination[i - 1][j - 1] + combination[i - 1][j]) % MOD_NUMBER;
				}
			}
		}
		sb.append(combination[N][K]);

		// 3. 출력
		System.out.println(sb.toString());

		br.close();
	}
	/*
	 * static int factorial(int N) { if (N<=1) { return 1; } return N *
	 * factorial(N-1); }
	 */
}

 

C++ 코드 : 

// 이항계수2 11051
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define NUMBER (10007)
#define MAX (1002)

int combi[MAX][MAX];
int N, K;   // 이항계수 NCK

int main() {
	scanf("%d %d", &N, &K);

	// 초기화
	combi[0][0] = combi[1][0] = combi[1][1] = combi[1][1] = 1;

	// 파스칼의 삼각형
	for (int i = 2; i <= N; i++)
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) {
				combi[i][j] = 1;
			}
			else {
				combi[i][j] = (combi[i - 1][j - 1] + combi[i - 1][j]) % NUMBER;
			}
		}
	// 출력
	printf("%d", combi[N][K]);
	return 0;
}
/*
int factorial(int N) {
	if (N == 0) {
		return 1;
	}
	return N * factorial(N - 1);
}
*/
#endif