시리즈 톺아보기

백준 알고리즘

다리 놓기

조건
문제
입력
출력
케이스

예제 1

풀이
Gotta Go FAST!
전체 소스
분류

다리 놓기 🔗

랭크	사용 언어

🔗 전체 1010번 문제

조건 🔗

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

문제 🔗

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

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

입력 🔗

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

출력 🔗

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

케이스 🔗

예제 1 🔗

입력

출력

0 1
1 5
2 67863915

풀이 🔗

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

$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개의 경우의 수가 존재한다. 이는 $_{5} C_{3}$ 의 계산 결과와 일치한다.

_{5} C_{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(메모이제이션)이란?
동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장해놓고 필요 시 사용하여 반복적인 연산 작업을 제거하는 기술.

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

_{n} C_{r} =_{n - 1} C_{r - 1} +_{n - 1} C_{r}

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

만약, $_{5} C_{3}$ 을 연산한다면 아래와 같이 진행된다.

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

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

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

전체 소스 🔗

JAVA

0 import java.io.BufferedReader;
1 import java.io.IOException;
2 import java.io.InputStreamReader;
3 
4 /**
5  * 백준 전체 1010 문제 알고리즘 클래스
6  *
7  * @author RWB
8  * @see <a href="https://blog.itcode.dev/posts/2021/06/09/a1010">1010 풀이</a>
9  * @since 2021.06.09 Tue 14:14:09
10  */
11 public class Main
12 {
13     // 다리 건설 경우의 수
14     private static final int[][] dp = new int[31][31];
15     
16     /**
17      * 메인 함수
18      *
19      * @param args: [String[]] 매개변수
20      *
21      * @throws IOException 데이터 입출력 예외
22      */
23     public static void main(String[] args) throws IOException
24     {
25         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
26         
27         // 케이스 수
28         int T = Integer.parseInt(reader.readLine());
29         
30         for (int i = 0; i < T; i++)
31         {
32             String[] temp = reader.readLine().split(" ");
33             
34             int N = Integer.parseInt(temp[0]);
35             int M = Integer.parseInt(temp[1]);
36             
37             System.out.println(combination(M, N));
38         }
39         
40         reader.close();
41     }
42     
43     /**
44      * 조합 결과 반환 함수
45      *
46      * @param n: [int] 원소 갯수
47      * @param r: [int] 조합 갯수
48      *
49      * @return [int] 조합
50      */
51     private static int combination(int n, int r)
52     {
53         // 이미 계산된 값일 경우
54         if (dp[n][r] > 0)
55         {
56             return dp[n][r];
57         }
58         
59         // 원소의 갯수가 조합의 갯수와 동일하거나 0일 경우
60         else if (n == r || r == 0)
61         {
62             return dp[n][r] = 1;
63         }
64         
65         // 일반적인 경우
66         else
67         {
68             return dp[n][r] = combination(n - 1, r - 1) + combination(n - 1, r);
69         }
70     }
71 }

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

$_{5} C_{0}$ , $_{5} C_{5}$ 와 같이 $_{n} C_{0}$ , $_{n} C_{n}$ 일 경우 그 값은 1이다. 해당 케이스의 경우 1을 반환한다. (전체를 선택하거나, 아무것도 선택하지 않는 방법은 하나뿐이다.)

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

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

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

분류 🔗

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

📆 작성일

2021-06-9 Wed 14:14:09

📚 카테고리

알고리즘

🏷️ 태그

백준

알고리즘

JAVA(자바)

Combination(조합)

SILVER

SILVER V

[백준 / JAVA] 백준 알고리즘 1009번 분산처리

[백준 / JAVA] 백준 알고리즘 1011번 Fly me to the Alpha Centauri

𝝅번째 알파카의 개발 낙서장

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

posts

알고리즘

시리즈 톺아보기

Table of Contents

다리 놓기 🔗

조건 🔗

문제 🔗

입력 🔗

출력 🔗

케이스 🔗

예제 1 🔗

풀이 🔗

Gotta Go FAST! 🔗

전체 소스 🔗

분류 🔗

0	import java.io.BufferedReader;
1	import java.io.IOException;
2	import java.io.InputStreamReader;
3
4	/**
5	* 백준 전체 1010 문제 알고리즘 클래스
6	*
7	* @author RWB
8	* @see <a href="https://blog.itcode.dev/posts/2021/06/09/a1010">1010 풀이</a>
9	* @since 2021.06.09 Tue 14:14:09
10	*/
11	public class Main
12	{
13	// 다리 건설 경우의 수
14	private static final int[][] dp = new int[31][31];
15
16	/**
17	* 메인 함수
18	*
19	* @param args: [String[]] 매개변수
20	*
21	* @throws IOException 데이터 입출력 예외
22	*/
23	public static void main(String[] args) throws IOException
24	{
25	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
26
27	// 케이스 수
28	int T = Integer.parseInt(reader.readLine());
29
30	for (int i = 0; i < T; i++)
31	{
32	String[] temp = reader.readLine().split(" ");
33
34	int N = Integer.parseInt(temp[0]);
35	int M = Integer.parseInt(temp[1]);
36
37	System.out.println(combination(M, N));
38	}
39
40	reader.close();
41	}
42
43	/**
44	* 조합 결과 반환 함수
45	*
46	* @param n: [int] 원소 갯수
47	* @param r: [int] 조합 갯수
48	*
49	* @return [int] 조합
50	*/
51	private static int combination(int n, int r)
52	{
53	// 이미 계산된 값일 경우
54	if (dp[n][r] > 0)
55	{
56	return dp[n][r];
57	}
58
59	// 원소의 갯수가 조합의 갯수와 동일하거나 0일 경우
60	else if (n == r \|\| r == 0)
61	{
62	return dp[n][r] = 1;
63	}
64
65	// 일반적인 경우
66	else
67	{
68	return dp[n][r] = combination(n - 1, r - 1) + combination(n - 1, r);
69	}
70	}
71	}