코딩 테스트/백준

[Baekjoon/백준] 11051번: 이항 계수 2(C/C++)

JongHoon 2022. 3. 30. 19:17

단계별로 풀어보기 17단계(정수론 및 조합론) 8번 문제

https://www.acmicpc.net/step/18

 

정수론 및 조합론 단계

N개의 물건 중 순서를 고려하지 않고 K개를 고르는 경우의 수, 이항 계수를 구하는 문제

www.acmicpc.net


백준 11051번: 이항 계수 2

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

 

11051번: 이항 계수 2

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

www.acmicpc.net


문제 설명

자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.


입력과 출력

입력: 첫째 줄 NK가 주어진다. (1 N ≤ 1,000, 0 K N)

출력: nCk를 10,007로 나눈 나머지를 출력한다.


접근 방법

이번 문제는 자연수 N과 정수 K를 입력받아 이항계수 nCk를 구해 이를 10,007로 나눈 나머지를 구해 출력하는 문제다.

이전 문제인 11050번(이항 계수 1)에서 N과 K의 입력 범위가 1000까지 증가했고, 또한 구한 이항 계수를 10007로 나눠서 나온 나머지를 구해야하는 것으로 바뀌었다. N과 K 범위가 증가했으므로, 이전 문제를 풀었던 것처럼 반복문을 이용한 팩토리얼 함수만 이용해서 문제를 해결하는 것은 불가능하다.

그러므로 이번 문제는 위의 공식과 2차원 배열(arr[N][K])을 이용한 다이나믹 프로그래밍으로 문제를 풀어야한다. 다이나믹 프로그래밍은 계산을 반복하지 않고 미리 저장된 값을 불러오는 것이다. 따라서 위 공식에 N과 K를 대입해 2차원 배열을 이용해서 arr[N][K] = arr[N-1][K-1] + arr[N-1][K]를 넣고, 문제에서 요구한 10007만큼 나눈 나머지 값을 넣어주는 식으로 진행하면 문제를 해결할 수 있다.


코드

#include <iostream>
using namespace std;
#define MAX 1001

int arr[MAX][MAX];

int main(int argc, char * argv[]) {
	int N, K;
	
	cin >> N >> K;

	arr[0][0] = arr[1][0] = arr[1][1] = 1;
	
	for (int i = 2; i <= N; i++)
		for (int j = 0; j <= i; j++) {
			if (j == 0)
				arr[i][0] = 1;
			else if (j == i)
				arr[i][j] = 1;
			else
				arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j]) % 10007;
		}

	cout << arr[N][K] << endl;

	return 0;
}

결과

백준 제출 결과