[BOJ] Q1328 고층 빌딩

[BOJ] Q1328 고층 빌딩

Question

Language: Python

Difficulty: Platinum 5

해당 문제는 2가지 측면으로 분리해서 고려해야한다.

1. 우선, 숲을 봐야한다. 즉, 빌딩을 배치하는 방법에 대해서 생각해봐야한다

1. 숲을 구성하는 나무를 봐야한다. 빌딩을 배치하기 위해 사용되는 빌딩 조합을 구해야한다.

Solution 1

from math import perm,comb,factorial
def print_list(lists):
    print("DI")
    for list in lists:
        print(list)
def solution():
    di=[[0] * num for _ in range(num)]
    
    #빌딩 개수가 1일 때의 경우를 따로 처리한다.
    if num==1:
        return 1
    
    di[1][1]=1
    #빌딩 배치를 구하기 위해 하위 조합들을 구해야한다.
    for i in range(2,num):
        di[i][1]=factorial(i-1)
        for j in range(2,i):
            temp=0
            for k in range(i-1,j-2,-1):
                temp+=di[k][j-1]*perm(i-1,i-1-k)

            di[i][j]=temp
        di[i][i]=1

    
    #빌딩 배치를 구하는 과정
    count=0
    if L==1:
        count=di[num-1][R-1]
    elif R==1:
        count=di[num-1][L-1]
    else:
        for i in range(num-2,L-2,-1):
            count+=(comb(num-1,i)*di[i][L-1]*di[num-i-1][R-1])

    return count % 1000000007    

if __name__ == "__main__":
    num,L,R=map(int,input().split()) 
    print(solution())

위의 방식은 조합을 활용한 방식이다 반면, DP 방법론적으로 접근을 해보면 아래와 같은 코드로 쉽게 접근할 수 있다.

dp풀이

Solution 2

N,L,R=map(int,input().split())
di=[[[0] *101 for _ in range(101)] for _ in range(101)]

di[1][1][1]=1
for n in range(2,N+1):
    for l in range(1,L+1):
        for r in range(1,R+1):
            di[n][l][r]=(di[n-1][l][r-1]+di[n-1][l-1][r]+di[n-1][l][r]*(n-2)) % 1000000007

print(di[N][L][R])