[백준] boj 1010 다리놓기(Cobination)

방법 1

#include <iostream>
#define MAX 31
int arr[MAX][MAX];

int main()
{   
	for(int i=0;i<MAX;i++) arr[i][0] = 1;
	for(int i=1;i<MAX;i++)
	{
		for(int j=1;j<=i;j++)
		{
			arr[i][j]=arr[i-1][j]+arr[i-1][j-1];
		}
	}
	int N;
	scanf("%d",&N);
	while(N--)
	{
		int r,n;
		scanf("%d %d",&r,&n);
		printf("%d\n",arr[n][r]);
	}
	return 0;
}

방법 2

#include <iostream>
#define MAX 31
 
int main()
{
	int N;
	scanf("%d",&N);
	while(N--)
	{
		int r,n;
		scanf("%d %d",&r,&n);
		int answer=1;
		for(int i=1;i<=r;i++)
		{
			answer=answer*(n-i+1)/i;
		}
		printf("%d\n",answer);
	}

	return 0;
}

힌트

1. 이 문제는 경우의 수(조합)문제입니다.

2. 방법1은 DP를 활용한 경우의수(조합)를 구하는 방법입니다. ( 규칙을 찾아보세요 ! )

3. 방법2는 DP를 사용하지 않고 조합을 찾아내는 식입니다.

문제링크 : https://www.acmicpc.net/problem/1010