[1. 문제 설명]
https://www.acmicpc.net/problem/1010
[2. 풀이 접근]
완전 탐색에서 시작한다.
다리가 교차되지 않기 위해서는 일정한 순서를 갖고 다리를 연결 해야 한다.
- 강 서쪽 에서 1번 다리와 강 동쪽에서 2번 다리를 연결
- 강 서쪽 2번 다리는 3번 다리 이후부터 연결 할 수 있음
- 강 서쪽 내 모든 다리가 이러한 규칙대로 모두 연결 된 경우 한가지 경우 완성
중복 문제
빨간색 구간이 어떻게 연결되든 화살표 이후 경우의 수에는 영향을 주지 않는다.
즉, 한번 계산해 놓은 값을 재활용 할 수 있다.
서쪽과 동쪽에서 연결 된 경우에 대해서 메모이제이션을 적용 할 수 있다.
[3. 코드]
'알고리즘 > Baekjoon' 카테고리의 다른 글
| 동적계획법. [11052] (0) | 2023.01.10 |
|---|---|
| 동적계획법. [9095 / 2193] (0) | 2023.01.07 |
| 분할정복. [2104] (0) | 2023.01.06 |
| 분할 정복. [1725] (0) | 2023.01.04 |
| 분할정복. [2261] (0) | 2023.01.03 |