[백준 / JAVA] 백준 알고리즘 1010번 다리 놓기

⏰ 2021-06-09 (수) 14:14:09

시리즈 모아보기

백준 알고리즘

12 / 23

Table of Contents

1. 다리 놓기

1.1. 조건

1.2. 문제

1.3. 입력

1.4. 출력

1.5. 케이스

1.5.1. 예제 1

2. 풀이

2.1. Gotta Go FAST!

2.2. 전체 소스

2.3. 분류

다리 놓기

랭크	사용 언어
	JAVA

🔗 🔗 전체 1010번 문제

조건

시간제한	메모리 제한
0.5초	128MB

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

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

입력

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

출력

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

케이스

예제 1

입력

출력

풀이

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

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

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

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

구분	$M_1$	$M_2$	$M_3$	$M_4$	$M_5$
1	O	O	O
2	O	O		O
3	O	O			O
4	O		O	O
5	O		O		O
6	O			O	O
7		O	O	O
8		O	O		O
9		O		O	O
10			O	O	O

총 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}$ 와 같은 모든 하위 조합들은 연산을 통째로 건너뛸 수도 있을 것이다.