[백준 1328] 고층 빌딩

문제의 N제한은 100이고, 100개의 건물의 배치하는 경우의 수는 100! 이기에 완전 탐색으로는 불가능하다.

따라서, 동적 계획법으로 푸는 문제이며 + 경우의 수 구하기 문제

즉, 각각의 경우를 따져가며 봐야한다.

(현재의 경우의 수 = 이전 가능한 경우의 수1 + 이전 가능한 경우의 수2 + ..... )

예를 들어, 건물이 3 2 4 가 있다면 1 을 추가할 수 있는 경우는

1. 왼쪽으로 추가하는 경우
2. 오른쪽으로 추가하는 경우
3. 건물 사이로 추가하는 경우( n개의 건물이 있으면 사이에 넣을 수 있는 방법은 n-2)

1번과 2번의 경우, 추가하는 쪽의 길이(left, Right)가 증가하는 것을 알 수 있다. ( 1 3 2 4, 3 2 4 1)

하지만 3번의 경우 길이의 변화는 없다. (ex. 3 1 2 4)

따라서 각 경우를 점화식으로 표현하면,

Dp(n, l, r) = Dp(n-1, l-1, r) + Dp(n-1, l, r-1) + DP(n-1, l, r) * (n-2) 

---

Review.

good