카카오 데이터 센터 화재로 티스토리 블로그가 접속이 안돼 백준 블로그를 이용합니다.

앳코더에서는 PS에서 자주 등장하는 동적 계획법 유형들을 26가지로 정리한 Educational DP Contest를 제공하고 있습니다.

이 블로그에서는 T번 문제인 Permutation의 풀이를 더 쉽게 이해할 수 있는 피드백을 제공합니다.

해당 문제를 검색했을 때 나오는 블로그에서는 점화식을 다음과 같이 설명하고 있습니다.

$dp_{i, j}$ := i번째 수까지 1, 2, ..., i를 써서 완성했을 때 i번째 원소가 j인 경우의 수

그리고 테이블을 채우는 방법은 다음 식으로 표현됩니다.

$$dp_{i, j} = \begin{cases} \sum\limits_{k = 1}^{j - 1} dp_{i - 1, k} & (s_{i - 1} = <) \\ \sum\limits_{k = j}^{i - 1} dp_{i - 1, k} & (s_{i - 1} = >) \end{cases}$$

하지만 저는 이해가 잘 되지 않았습니다. 왜냐하면 순열 중간에 i보다 큰 원소가 당연히 낄 수 있는데 설명에서는 이를 고려하지 않고 원소 집합을 $\{1, 2,..., i\}$로 고정했기 때문입니다.

설명에는 첫 i - 1개의 수를 1,... , i - 1로 고정하면서 전이를 한다고 했지만 잘 와닿지 않았습니다. 저는 설명을 곱씹어 봤고, 기존의 설명을 더 직관적으로 이해하기 위해선 점화식을 다음과 같이 정의해야 한다는 결론을 내렸습니다.

$dp_{i, j}$ := i번째 원소까지 완성했을 때 i번째 수가 j번째로 작은 수일 경우의 수

이러면 테이블을 채우는 방법이 완벽히 설명됩니다.

문자가 <일 경우 j보다 작은 순서의 원소들, 즉 순서(순위)가 [1, j - 1]인 원소로 끝나는 경우의 수를 더한다고 이해할 수 있습니다.

문자가 >일 경우는 i - 1개의 원소에 더해 추가했을 때 마지막 원소는 j번째로 작은 원소가 된다는 뜻입니다. 그러면 원소를 추가하지 않았을 때 j번째로 작은 원소를 $j_{old}$라고 합시다. j를 추가하면 $j_{old}$의 순서는 하나 증가한 $j_{old} + 1$이 됩니다. 이런식으로 기존의 원소들의 순위가 하나씩 밀리고 이에 대한 계산은 $\sum\limits_{k = j}^{i - 1} dp_{i - 1, k}$으로 치환됩니다.

이렇게 n번째 원소까지 채우면 조건을 만족하는 순열의 개수를 모두 구할 수 있게 됩니다.

설명에 틀린 부분이 있을 수 있습니다. 설명에 잘못된 부분을 지적해주시거나 더 좋은 설명을 댓글로 알려주신다면 오류도 고칠 수 있고 추후 저와 같은 의문을 가졌던 분이 시행착오를 줄일 수 있어 큰 도움이 될 것 같습니다.