다리 놓기

---

🔗 🔗 전체 1010번 문제

조건

---

문제

---

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 $N$개의 사이트가 있고 동쪽에는 $M$개의 사이트가 있다는 것을 알았다. $(N ≤ M)$

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 ($N$개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

---

입력의 첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 $N$, $M$ $(0 < N ≤ M < 30)$이 주어진다.

출력

---

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

케이스

---

예제 1

---

• 입력

TC
1
2
3
4
3
2 2
1 5
13 29

• 출력

TC
1
2
3
1
5
67863915

풀이

---

규칙을 정리하면 아래와 같다.

1. $N$구역에서 $M$구역으로 다리를 건설한다.
2. $N <= M$이다.
3. 사이트 당 연결된 다리는 하나다.
4. 다리끼리는 서로 겹쳐서 연결되면 안 된다.

1000번 부터 문제 풀면서, 🔗 1007번 벡터로 인해 조합이라는 키워드를 쉽게 연상할 수 있었다. 문제에서 $N$구역에서 $M$구역으로 다리를 건설한다고 서술하므로 $N$을 기준으로 생각하기 쉽다. 반대로 $M$을 기준으로 생각하면 해결의 실마리가 보인다. $M$구역의 사이트에서 $N$구역의 사이트 갯수만큼 연결할 사이트에 대한 조합을 계산하면 되기 때문.

예를 들어 $N$구역에 3개의 사이트가 있고, $M$구역에 5개의 사이트가 있다고 가정하자.

총 10개의 경우의 수가 존재한다. 이는 $_5C_3$의 계산 결과와 일치한다.

$$_5C_3 = \frac{5!}{3! \times 2!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (2 \times 1)} = \frac{5 \times 4}{2 \times 1} = 10$$

메모

❓ 숫자가 왜 감탄(!)을 하죠?
Factorial(팩토리얼) 연산자로 $n! = n \times (n - 1) \times (n - 2) \times ... \times 1$과 같은 형태로 연산한다.

더도말고 덜도말고 조합 알고리즘을 설계하면 된다. 조합의 요소를 반환할 필요 없이, 조합의 갯수만 구하면 되므로 🔗 1007번 벡터문제보다 더 간단하다.

Gotta Go FAST!

---

무턱대로 위 식으로 조합 알고리즘을 짜면 시간 초과 오류를 볼 수 있다. 그도 그럴 것이, 원리 자체는 쉽지만 시간제한이 0.5s로 매우 짧기 때문. $M$의 값이 최대 30이므로, 최대 $30!$에 대한 연산을 수행해야하기 때문이다. 그러므로 Memoization(메모이제이션)이라는 최적화를 적용해야 한다.

메모

❓ Memoization(메모이제이션)이란?
동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장해놓고 필요 시 사용하여 반복적인 연산 작업을 제거하는 기술.

조합을 재귀적으로 표현하면 아래와 같이 표현할 수 있다.

$$_nC_r = _{n-1}C_{r-1} + _{n-1}C_r$$

아래의 그림을 보면 이해하기 쉽다.

만약, $_5C_3$을 연산한다면 아래와 같이 진행된다.

이 중, $_3C_2$의 경우 $_4C_2$, $_4C_3$을 계산할 때 필요하므로 여러번 호출된다. 만약, 메모이제이션이 적용되지 않았다면, $_3C_2$이 필요할 때마다 1에서부터 다시 연산해야한다. $_{30}C_{14}$와 같이 숫자가 커지면 위 그림의 깊이도 깊어지기 때문에 많은 오버헤드가 발생한다.

만약 이렇게 연산된 값을 버리지 않고 메모리상에 저장한 뒤 쓸 수 있다면 연산에서 엄청난 이점이 발생한다. $_3C_2$을 이미 저장했다면 $_4C_2$, $_4C_3$을 계산할 때 저장된 $_3C_2$을 즉시 꺼내 사용할 수 있다. 복잡한 연산을 건너뛸 수 있으며, 동일한 값이 여러번 호출되도 상관없다.

해당 문제의 조합 알고리즘의 연산에서 한 번 연산된 값을 임의의 배열에 저장하여 이를 활용하면 0.5초라는 짧은 시간을 충족할 수 있을 것이다.

전체 소스

---

JAVA
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 백준 전체 1010 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/09/a1010">1010 풀이</a>
 * @since 2021.06.09 Tue 14:14:09
 */
public class Main
{
	// 다리 건설 경우의 수
	private static final int[][] dp = new int[31][31];
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// 케이스 수
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			String[] temp = reader.readLine().split(" ");
			
			int N = Integer.parseInt(temp[0]);
			int M = Integer.parseInt(temp[1]);
			
			System.out.println(combination(M, N));
		}
		
		reader.close();
	}
	
	/**
	 * 조합 결과 반환 함수
	 *
	 * @param n: [int] 원소 갯수
	 * @param r: [int] 조합 갯수
	 *
	 * @return [int] 조합
	 */
	private static int combination(int n, int r)
	{
		// 이미 계산된 값일 경우
		if (dp[n][r] > 0)
		{
			return dp[n][r];
		}
		
		// 원소의 갯수가 조합의 갯수와 동일하거나 0일 경우
		else if (n == r || r == 0)
		{
			return dp[n][r] = 1;
		}
		
		// 일반적인 경우
		else
		{
			return dp[n][r] = combination(n - 1, r - 1) + combination(n - 1, r);
		}
	}
}

$dp[n][r]$는 int형 배열이므로 기본값이 0이다. 즉, $dp[n][r] > 0$일 경우 $_nC_r$가 이미 계산되었다는 뜻이므로, 이미 저장된 값을 반환한다.

$_5C_0$, $_5C_5$와 같이 $_nC_0$, $_nC_n$일 경우 그 값은 1이다. 해당 케이스의 경우 1을 반환한다. (전체를 선택하거나, 아무것도 선택하지 않는 방법은 하나뿐이다.)

나머지 일반적인 경우 $_nC_r$의 재귀적 표현 방식인 $_{n-1}C_{r-1} + _{n-1}C_{r}$을 적용하면 된다.

또한 $dp$ 이차원 배열은 31행렬로 초기화되는데, 그 이유는 $dp$의 행렬이 되는 $N$과 $M$의 최대값이 30이기 때문. 배열은 인덱스가 0부터 시작하므로 1을 더해야 한다.

또한 케이스별로 $dp$를 초기화하지 않는데, 이는 조합이 범용적이므로 재사용이 가능하기 때문이다. 1번 케이스나 100번 케이스나 $_5C_3$의 값은 10이다. 따라서 초기화를 하지 않으면 오히려 이전 케이스에서 계산했던 내용을 그대로 사용할 수 있어서 이득이다. 만약 첫 번째 케이스에서 $_{30}C_{12}$와 같이 큰 수를 계산했다면, 이후 케이스의 $_{12}C_{5}$와 같은 모든 하위 조합들은 연산을 통째로 건너뛸 수도 있을 것이다.

분류

---

• 수학
• 다이나믹 프로그래밍
• 조합론