[백준 25384] 니은숲 예술가 (Diamond V)

https://www.acmicpc.net/problem/25384

25384번: 니은숲 예술가

 

조형물의 상태로 가능한 것을 아무거나 하나 그려 보았다. 그림과 같이, 네 면 중 인접한 두 면에는 가장 마지막 조각만이 있고, 나머지 두 면에는 연속된 여러 개의 조각들이 나타난다. 따라서 부분 문제를 다음과 같이 정의할 수 있겠다.

 - \( DP(n, i, j) \) : 네 면 중 두 면에 n번째 조각이 나타나고, 한 면에 i~n번째 조각이, 한 면에 j~n번째 조각이 나타남.

n = 4, (조각) = {1, 2, 3, 1}을 기준으로 이 DP 식이 어떻게 흘러가는지 살펴보자.

n = 1	j = 0
i = 0	1

Base Case다. 0번째 조각은 니은 모양이 아니기 때문에 특수성이 있어서 1번째 조각을 Base Case로 잡아야 한다. Base Case의 모양은 다음과 같다. (가짓수가 1개뿐이라는 사실은 자명하다.)

2번째 조각을 붙였을 때 그림은 다음과 같다.

n = 2	j = 0	j = 1
i = 0	1	1
i = 1	1	1

이제 3번째 조각을 붙일 차례다. 만약 0번째 조각과 3번째 조각의 번호가 다르다면, DP-table은 다음과 같이 되었을 것이다.

n = 3	j = 0	j = 1	j = 2
i = 0	1	1	2
i = 1	1	1	2
i = 2	2	2	4

왜 그런가? 위의 4가지 그림에 3번째 조각을 일일이 붙여 보면 알 수 있을 것이다. 그리고 조각을 직접 붙여 보면 알겠지만, 다음의 중요한 사실을 얻는다.

$$ DP(n + 1, i, j) = DP(n, i, j) $$

왜냐하면 \( DP(n, i, j) \)로부터 \( DP(n + 1, i, j) \)를 만드는 방법은 n + 1번째 조각을 붙일 때 n번째 조각과 완전히 똑같은 모양으로 붙이는 방법밖에 없기 때문이다. 그렇다면, n + 1번째 조각을 n번째 조각과 완전히 반대 방향으로 붙이면 무엇을 얻을까? 다음 식을 얻는다.

$$ DP(n, n - 1, n - 1) = \sum_{i, j < n - 1} DP(n, i, j) $$

나머지 케이스도 각각 다음 점화식을 얻는다.

$$ DP(n, i, n - 1) = \sum_{j < n - 1} DP(n, i, j) $$

$$ DP(n, n - 1, j) = \sum_{i < n - 1} DP(n, i, j) $$

이 점화식을 그대로 따라가면 저 테이블이 생성된다는 것을 알 수 있다. 경우의 수는 표에 나와 있는 모든 값을 더한 16가지다.

다시 원래대로 돌아와서, 0번째 조각과 3번째 조각의 번호가 같다면? 점화식의 sum 부분에서 인덱스가 0부터 시작하는 것이 아니라 1부터 시작해야 한다는 사실을 알 수 있다. 이는 0번째 조각과 3번째 조각의 번호가 같고, 0번 다음 번호가 1번이기 때문이다. 이 점을 고려해서 일반적인 점화식을 짜 주도록 하자. DP-table의 모습은 다음과 같다.

n = 3	j = 0	j = 1	j = 2
i = 0	1	1	1
i = 1	1	1	1
i = 2	1	1	1

sum의 인덱스가 0이 아닌 1부터 시작하기에 새로 업데이트된 모든 값이 1이 되었다. 경우의 수는 표에 나와 있는 모든 값을 더한 9이다.

* 예외 케이스 : 번호가 같은 인접한 두 조각이 있다면 저 DP 식 자체가 성립하지 않는다. 그럴 땐 그냥 0을 출력하고 리턴해야 한다.

3차원 DP임에도 불구하고 보기 드물게 공간복잡도가 O(n^2)이다. 이는 DP(n, i, j)에서 사실상 n을 굳이 저장할 필요가 없기 때문이다. 이는 표가 확장되는 모습에서도 알 수 있다. 시간복잡도는 naiive하게 계산하면 O(n^4)일 테지만, 주어진 모든 식이 2차원 누적 합이기 때문에 누적 합 테이블을 따로 만들어서 관리해줄 수 있다. 그러면 테이블 만드는 시간 O(n^2), 계산하는 시간 O(1) 해서, 시간복잡도도 O(n^2)을 얻는다.