- [백준 / JAVA] 백준 알고리즘 1021번 회전하는 큐
- [백준 / JAVA] 백준 알고리즘 1020번 디지털 카운터
- [백준 / JAVA] 백준 알고리즘 1019번 책 페이지
- [백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기
- [백준 / JAVA] 백준 알고리즘 1017번 소수 쌍
- [백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수
- [백준 / JAVA] 백준 알고리즘 1015번 수열 정렬
- [백준 / JAVA] 백준 알고리즘 1014번 컨닝
- [백준 / JAVA] 백준 알고리즘 1013번 Contact
- [백준 / JAVA] 백준 알고리즘 1012번 유기농 배추
- [백준 / JAVA] 백준 알고리즘 1011번 Fly me to the Alpha Centauri
👀 [백준 / JAVA] 백준 알고리즘 1010번 다리 놓기
- [백준 / JAVA] 백준 알고리즘 1009번 분산처리
- [백준 / JAVA] 백준 알고리즘 1008번 A / B
- [백준 / JAVA] 백준 알고리즘 1007번 벡터
- [백준 / JAVA] 백준 알고리즘 1006번 습격자 초라기
- [백준 / JAVA] 백준 알고리즘 1005번 ACM Craft
- [백준 / JAVA] 백준 알고리즘 1004번 어린 왕자
- [백준 / JAVA] 백준 알고리즘 1003번 피보나치 함수
- [백준 / JAVA] 백준 알고리즘 1002번 터렛
- [백준 / JAVA] 백준 알고리즘 1001번 A - B
- [백준 / JAVA] 백준 알고리즘 1000번 A + B
- 백준 알고리즘 시작하기
다리 놓기 🔗
조건 🔗
시간제한 | 메모리 제한 |
---|---|
0.5초 | 128MB |
문제 🔗
재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 개의 사이트가 있고 동쪽에는 개의 사이트가 있다는 것을 알았다.
재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.
입력 🔗
입력의 첫 줄에는 테스트 케이스의 개수 가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 , 이 주어진다.
출력 🔗
각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.
케이스 🔗
예제 1 🔗
- 입력
TC
0 | 3 |
1 | 2 2 |
2 | 1 5 |
3 | 13 29 |
- 출력
TC
0 | 1 |
1 | 5 |
2 | 67863915 |
풀이 🔗
규칙을 정리하면 아래와 같다.
- 구역에서 구역으로 다리를 건설한다.
- 이다.
- 사이트 당 연결된 다리는 하나다.
- 다리끼리는 서로 겹쳐서 연결되면 안 된다.
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(메모이제이션)이란?
동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장해놓고 필요 시 사용하여 반복적인 연산 작업을 제거하는 기술.
조합을 재귀적으로 표현하면 아래와 같이 표현할 수 있다.
아래의 그림을 보면 이해하기 쉽다.
만약, 을 연산한다면 아래와 같이 진행된다.
이 중, 의 경우 , 을 계산할 때 필요하므로 여러번 호출된다. 만약, 메모이제이션이 적용되지 않았다면, 이 필요할 때마다 1에서부터 다시 연산해야한다. 와 같이 숫자가 커지면 위 그림의 깊이도 깊어지기 때문에 많은 오버헤드가 발생한다.
만약 이렇게 연산된 값을 버리지 않고 메모리상에 저장한 뒤 쓸 수 있다면 연산에서 엄청난 이점이 발생한다. 을 이미 저장했다면 , 을 계산할 때 저장된 을 즉시 꺼내 사용할 수 있다. 복잡한 연산을 건너뛸 수 있으며, 동일한 값이 여러번 호출되도 상관없다.
해당 문제의 조합 알고리즘의 연산에서 한 번 연산된 값을 임의의 배열에 저장하여 이를 활용하면 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 | } |
는 int형 배열이므로 기본값이 0이다. 즉, 일 경우 가 이미 계산되었다는 뜻이므로, 이미 저장된 값을 반환한다.
, 와 같이 , 일 경우 그 값은 1이다. 해당 케이스의 경우 1을 반환한다. (전체를 선택하거나, 아무것도 선택하지 않는 방법은 하나뿐이다.)
나머지 일반적인 경우 의 재귀적 표현 방식인 을 적용하면 된다.
또한 이차원 배열은 31행렬로 초기화되는데, 그 이유는 의 행렬이 되는 과 의 최대값이 30이기 때문. 배열은 인덱스가 0부터 시작하므로 1을 더해야 한다.
또한 케이스별로 를 초기화하지 않는데, 이는 조합이 범용적이므로 재사용이 가능하기 때문이다. 1번 케이스나 100번 케이스나 의 값은 10이다. 따라서 초기화를 하지 않으면 오히려 이전 케이스에서 계산했던 내용을 그대로 사용할 수 있어서 이득이다. 만약 첫 번째 케이스에서 와 같이 큰 수를 계산했다면, 이후 케이스의 와 같은 모든 하위 조합들은 연산을 통째로 건너뛸 수도 있을 것이다.
분류 🔗
- 수학
- 다이나믹 프로그래밍
- 조합론
📆 작성일
2021-06-9 Wed 14:14:09
📚 카테고리
🏷️ 태그