[ICPC 본선 대비 뇌셋] Day 12

전자기 공부 할 바에야 CERC 문제들을 풀어보고 있다.

백준 13948 Dancing Disks www.acmicpc.net/problem/13948

13948번: Dancing Disks

뭔가 아리까리 하긴 한데, 입력 수열에 제한이 없어보이는 느낌을 받을 수 있다. 실제로 모든 경우의 수열이 다 된다.

[정의 1] 한 점 (i, j)에서 증가하는 수열이란 base부터 봤을 때 증가하는 수열이다. 감소하는 수열도 마찬가지로 정의된다.

[정의 2] 점들의 크기관계 (i, j) < (k, l)는 i<=k and j<l and (not (i, j) == (k, l))이다.

[관찰 1] 점 A1, .., Ak위치에 증가하는 수열들이 있다면, 증가하는 수열들이 위치한 점보다 큰 점의 위치에서 감소수열을 만들 수 있다. 정 반대의 논의도 똑같이 적용 가능하다.

[풀이] (0, 0)에 길이 n인 임의의 배열 있을 때, (i, j)로 증가하는 순서로 옮길 수 있다면, 이러한 n의 최댓값을 A[i][j]라고 하자. 우리는 A[i][j]의 하한 B[i][j]을 구할 것이다. 또한 각 옮기는 과정은 constructive하게 재현될 수 있다.

B[i][j] = sum(B[k][l] : (k,l)<(i,j))

초항은 다음과 같다.

B[0][0] = A[0][0] = 1

B[0][1] = A[0][1] = 2

B[1][0] = A[1][0] = 2

점화식으로 B[5][5]의 하한을 구하면, 42960이 나오고, 40000보다 크므로 모든 경우를 다 만들 수 있음이 보장된다. 구현은 재귀로 짜면 되고, 모든 숫자가 12번 이하로 움직이므로 시간복잡도는 걱정할 필요 없다.

물론 실제 상한값은 훨씬 크다. 예상으로는 2^(n^2)일것 같지만 아닐거같기도 하다. 일단 A[0][2]만 봐도 3이 아니라 4가 가능하다.