[Algo Rhythm🕺💃]BOJ 1620 - 정상 회담2

문제 분석

문제를 분석하는 효과적인 방법들 중 하나는 그림으로 표현해보는 것이다. 이 문제에서 N = 0, 2, 4, 6 일때 완벽하게 악수하는 경우들과 그 수를 그림으로 표현하면 아래와 같다. (이때 각 국가의 대표는 노드로 표현했다.)

 

그림에서 검은색 노드와 흰색 노드가 연결된 선분을 기준으로 왼쪽 영역을 $l$, 오른쪽 영역을 $r$라고 하자. 그리고 $a$개의 노드들이 완벽하게 악수할 수 있는 경우의 수를 $f(a)$라고 하자. 그렇다면 N =0, 2, 4, 6일때 완벽하게 악수할 수 있는 경우의 수는 아래와 같은 규칙이 있음을 알 수 있다.

 

이 규칙을 점화식으로 표현하면 다음과 같다.

$f(N)= \begin{cases} 1, & if\ n = 0\\ \sum_{i=0}^{N-2} f(i) \times f(N-i-2)\ (i\ is\ even), & if\ n \gt 0 \end{cases}$

 

이를 재귀함수로도 구현할 수 있지만 중복된 계산들이 존재하기 때문에 효율적이지 않다. 이를 해결하기 위해 bottom up방식의 dynamic programming을 사용할 수 있다.

 

참고로 이 문제는 결국 $N / 2$번째 카탈랑수를 구하는 문제이다. 카랑랑수 문제에 관한 설명은 이 링크를 참고하길 바란다.

 

문제 풀이

문제 분석에서 구한 점화식은 이중 반복문을 통해 bottom-up방식으로 구현할 수 있다. 문제에서 요구하는 것은 주어진 N명의 대표들이 완벽하게 악수하는 경우의 수를 987654321로 나눈 나머지를 출력하는 것이기 때문에 이에 유의하여 구현하면 답을 구할 수 있다.

 

복잡도 분석

각 국가의 대표들의 수가 n일 때 시간복잡도와 공간복잡도는 다음과 같다.

 

시간복잡도 : $O(n^2)$ - memoization table의 수는 n개이고 각각을 구하는데 $O(n)$이 걸리기 때문에

공간복잡도 : $O(n)$ - memoization table의 수가 n이기 때문에

 

코드

1. Using DP

2. Using DP with space optimization

 

문제 출처 및 원본 문서

문제 출처 : www.acmicpc.net/problem/1670

1670번: 정상 회담 2

원본 문서 : www.notion.so/BOJ-1620-2-e60bb4885228465eb7dbcec7d7958644

BOJ 1620 - 정상회담2