[BOJ, 백준] 8895 막대배치 Python

 

조합론 문제를 덜 풀었길래 ... 조합론 문제를 찾다보니 이런 친구를 찾았습니다.

 

아이디어는 다음과 같습니다.

 

처음에 3차원 array를 만들어줍니다. (dp로서 문제를 해결하기 위해)

 

첫번째 인덱스는 막대의 갯수 / 두번째 인덱스는 왼쪽에서 봤을때의 개수 / 세번째 인덱스는 오른쪽에서 봤을때의 개수 입니다.

 

초기값 설정을 위해, dp[1][[1][1]은 1개가 되는 것으로 설정을 해둡니다.

이후 다음과 같이 생각할 수 있겠습니다.

 

dp[i][j][k]는 블럭이 i개, 왼쪽에서 봤을 때 j개 / 오른쪽에서 봤을 때 k개가 됩니다.

이때 블럭은 다음과 같이 나타낼 수 있습니다.

첫번째 오는 블럭의 높이를 h_1이라고 하고 두번째는 h_2 ... 마지막은 h_i 라고 합니다.

 

이때, 왼쪽에서 봤을 때 j개 라는 것은

h_1 = h_(l_1) < h_(l_2) < h_(l_3) < ... < h_(l_j) 

(단, 1 <= l_1 < l_2  <  .... < l_j <= i )

 

반대로, 오른쪽에서 봤을 때 k개 라는 것은

h_(r_k) > h_(r_(k-1)) >  .... > h_(r_2) > h_(r_1) = h_i

(단, 1 <= r_k < r_(k-1) < .... < r_1 <= i)

라는 뜻이 되겠습니다.

 

이 상황에서, 모든 블럭의 높이를 +1씩 해도 위의 2개의 부등식은 바뀌지 않을 것입니다.

예를 들어보면

 

주어진 블럭의 높이가 

2 4 3 1 이라면 i = 4, j = 2, k = 3입니다.

j = 2 : 2 < 4 (인덱스 (l_x에 해당하는 부분)는 1 <= 1 < 2 <= 4)

k = 3 : 4 > 3 > 1 (인덱스 (r_x에 해당하는 부분)는 1 <= 2 < 3 < 4 <= 4)

 

이제 다음 스텝을 생각한다면 모든 블럭의 높이를 1씩 올린다 했으므로 3 5 4 2가 되겠습니다.

이렇게 해도 변화는 없겠습니다.

 

이제 높이가 1인 블럭을 어디에 넣느냐? 가 중요해집니다.

 

1. 가장 왼쪽에 넣을 때

1 3 5 4 2 가 되면서

i = 5, j = 3, k = 3이 되겠습니다. (i, j가 1씩 늘어났습니다.)

 

2. 가장 오른쪽에 넣을 때

3 5 4 2 1이 되면서

i = 5, j = 2, k = 4가 되겠습니다. (j, k가 1씩 늘어났습니다.)

 

3. 그 외에 넣을 때

3 1 5 4 2 i = 5, j = 2, k = 3

3 5 1 4 2 i = 5, j = 2, k = 3

3 5 4 1 2 i = 5, j = 2, k = 3 (i만 1이 늘어났습니다.)

 

그렇다면 이러한 상황을 코드로 작성한다면 다음과 같이 되겠습니다.

import sys
input = sys.stdin.readline

T = int(input())
for _ in range (0,T):
    n,l,r = map(int,input().split())
    dp = [[[0 for _ in range (0,r+2)] for _ in range (0,l+2)] for _ in range (0,n+2)]
    dp[1][1][1]= 1
    for i in range (2, n+1):
        for j in range (1, l+1):
             for k in range (1, r+1):
                dp[i][j][k] += dp[i - 1][j - 1][k]
                dp[i][j][k] += dp[i - 1][j][k - 1]
                dp[i][j][k] += dp[i - 1][j][k] * (i - 2)

    print(dp[n][l][r])