문제 : https://www.acmicpc.net/problem/2407

Key Points

이 문제를 풀기 위해서는 먼저 순열과 조합의 개념에 대해 알고 있어야 한다.

  • 순서가 있는 경우 : 순열(Permutation) [서로 다른 n 개 중 r 개를 뽑아서 나열하는 경우]
  • 순서가 없는 경우 : 조합(Combination) [서로 다른 n 개 중 r 개를 뽑는 경우]

아래와 같은 방법으로 계산한다.

이 문제는 메모이제이션이라는 방법을 이용하여 조합의 공식에 따라서 구했다.

Explain

Memoization(메모이제이션)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

메모이제이션을 이용하면 조합의 값을 구하기 위해 파스칼 삼각형의 꼭대기까지 올라갈 필요 없이 바로 좌우측 상단의 값을 메모리에서 불러와 이용할 수 있다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Exam2407 {

	public static void main(String[] args) throws IOException {
		BigInteger[][] list;
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BigInteger big = new BigInteger("1");
		
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new BigInteger[10001][10001];
		list[1][0] = list[1][1] = big;
		
		for(int i=2;i<=n;i++) {
			for(int j=0;j<=i;j++) {
				if(i == j || j == 0) {
					list[i][j] = big;
				}else {
					list[i][j] = list[i-1][j-1].add(list[i-1][j]);
				}
			}
		}
		
		System.out.println(list[n][m]);
		
	}

}