BOJ 28287번 - 계단 자르기

28287번: 계단 자르기

UCPC 2023 예비소집 B번 문제이다.

아름다운 조합론 풀이가 있는 것 같은데 나는 잘 모르겠다.

때문에 내 방식대로 조금 복잡하게 풀이한다.

 

기본적인 관찰부터 시작하자.

먼저 크기 n의 계단을 직사각형으로 나누려면 최소 n개의 직사각형이 필요하다.

한 직사각형이 (i, i)와 (j, j)를 동시에 포함할 수 없기 때문이다.

 

크기 n의 계단을 n개의 직사각형으로 나누는 경우의 수 C(n)은 카탈란 수와 동일하다.

(n, n)을 포함하는 직사각형을 배치하는 방법은 n개이다.

이 직사각형을 r이라고 하고 r의 가로 길이를 w라고 하자.

 

r의 왼쪽 끝선을 기준으로 나머지 단위 정사각형들은 두 개의 영역으로 나누어진다.

따라서 나머지 단위 정사각형들을 (n - 1)개의 직사각형으로 나누는 경우의 수는 C(w - 1) * C(n - w)이 된다.

이를 이용하면 다음과 같은 점화식을 세울 수 있는데 이는 카탈란 수의 점화식과 동일하다.

C(n) = C(0) * C(n - 1) + C(1) * C(n - 2) + ... + C(n - 1) * C(0)

 

이제 원본 문제와 같이 크기 n의 계단을 (n + 1)개의 직사각형으로 나누어보자.

그 전에 새로 추가되는 직사각형은 n번째 행에만 배치된다고 가정하자.

그리고 n번째 행을 이루는 각 영역의 가로 길이를 순서대로 w_1, w_2, ..., w_k라고 하자.

각 영역의 끝선을 기준으로 상단의 나머지 단위 정사각형들도 k개의 영역으로 나누어진다.

이때의 경우의 수는 다음과 같이 계산할 수 있다.

cnt = 1;

for i = 1; i <= k; ++i

    cnt *= (i번째 영역이 새로 추가된 직사각형) ? C(w_i) : C(w_i - 1);

 

w = [3, 2, 3, 2]이고 2번째 영역은 새로 추가된 직사각형이라고 가정하자.

a

aa

aaa

aaa b

aaa bb

aaa bb c

aaa bb cc

aaa bb ccc

aaa bb ccc d

aaa bb ccc dd

 

모양이 강제되는 부분은 빨간색으로 표시하였다.

i번째 영역을 이루는 w_i개의 직사각형 중 마지막 직사각형은 밑변의 길이를 w_i로 만들기 위하여 모양이 강제된다.

나머지 (w_i - 1)개의 직사각형은 자유롭게 배치할 수 있으므로 경우의 수는 C(w_i - 1)이 된다.

하지만 i번째 영역이 새로 추가된 직사각형일 경우 w_i개의 직사각형 모두 자유롭게 배치할 수 있다.

따라서 이때의 경우의 수는 C(w_i)가 된다.

 

예외가 있는데 새로 추가된 직사각형이 (k - 1)번째 영역인 경우에는 다음과 같이 계산해야 한다.

cnt = C(w_k-1 + w_k - 1);

for i = 1; i <= k - 2; ++i

    cnt *= C(w_i - 1);

 

w = [3, 2, 3, 2]이고 3번째 영역은 새로 추가된 직사각형이라고 가정하자.

a

aa

aaa

aaa b

aaa bb

aaa bb c

aaa bb cc

aaa bb ccc

aaa bb cccd

aaa bb cccdd

 

모양이 강제되는 부분은 빨간색으로 표시하였다.

c와 d는 서로 다른 영역이지만 두 영역을 합쳐서 생각해도 밑변의 모양에 영향을 주지 않는다.

따라서 이때는 C(w_k-1 + w_k - 1)과 같이 계산해야 한다.

 

이렇게 n번째 행에 새로운 직사각형을 추가하는 경우의 수를 구할 수 있다.

여기서 행을 추가로 배치할 때의 경우의 수를 구할 수 있다면 문제를 해결할 수 있다.

이때는 오직 밑변의 개수에만 집중하면 된다.

기존 밑변의 개수를 c라고 하면 행을 하나 추가하였을 때의 밑변의 개수는 1개 이상 (c + 1)개 이하가 된다.

 

모든 내용을 종합하면 다음과 같은 점화식을 세울 수 있다.

dp[0][i][j] = 새로운 직사각형을 배치하지 않고 i번째 행에서 j개의 밑변을 갖는 경우의 수

dp[1][i][j] = i번째 행에 새로운 직사각형을 배치하고 j개의 밑변을 갖는 경우의 수

 

초기항은 다음과 같다.

dp[0][i][1] = C(i - 1)

dp[1][i][2] = (i - 1) * C(i - 1)

나머지 항의 구체적인 계산 과정은 생략한다.

적절히 계산한 후 dp[1][i][j]를 dp[1][i + 1][1 .. (j + 1)]에 전파해주면 답을 구할 수 있다.

 

끝