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

screen

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

posts

알고리즘

시리즈 톺아보기

백준 알고리즘

백준 알고리즘
count

다리 놓기 🔗

랭크 사용 언어
image JAVA

🔗 전체 1010번 문제

조건 🔗

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

문제 🔗

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

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

image

입력 🔗

입력의 첫 줄에는 테스트 케이스의 개수 가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 , 이 주어진다.

출력 🔗

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

케이스 🔗

예제 1 🔗

  • 입력

TC

03
12 2
21 5
313 29
  • 출력

TC

01
15
267863915

풀이 🔗

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

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

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

예를 들어 구역에 3개의 사이트가 있고, 구역에 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개의 경우의 수가 존재한다. 이는 의 계산 결과와 일치한다.

숫자가 왜 감탄(!)을 하죠?
Factorial(팩토리얼) 연산자로 과 같은 형태로 연산한다.

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

Gotta Go FAST! 🔗

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

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

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

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

image

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

image

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

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

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

전체 소스 🔗

JAVA

0import java.io.BufferedReader;
1import java.io.IOException;
2import 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 */
11public 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}

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

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

나머지 일반적인 경우 의 재귀적 표현 방식인 을 적용하면 된다.

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

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

분류 🔗

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