[1328번] 고층 빌딩 (빌딩 순서 구하기, 3차원 DP)
·
Coding Test/DP
1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 분석 D[N][L][R] : N개의 빌딩이 있고 왼쪽에서 볼 때 L개, 오른쪽에서 볼 때 R개가 가능한 경우의 수 가장 작은 빌딩을 N번째로 배치한다고 가정 가장 앞에 배치 : D[N][L][R] = D[N-1][L-1][R] ← 왼쪽에서 보이는 갯수가 +1 가장 뒤에 배치 : D[N][L][R] = D[N-1][L][R-1] ← 왼쪽에서 보이는 갯수가 +1 가운데에 배치 : D[N][L][R] = D[N-1][L][R] * (N-2) ← 보이는 갯수 동일, 가..