백준 1328 c++ -고층 빌딩

[필자 생각]

 

1차원과 2차원 배열로만 동적프로그래밍을 생각해왔다. 
아무리 생각해도 해답이 나오지 않아 자료들을 찾게 되었다.

[깨달음]

 

이 문제는 처음으로 내게 3차원 동적프로그래밍의 사고를 열어준 문제였다.

 

[문제 풀이]

 

D[N][L][R] 의 배열을 만들어 준다.

N의 갯수가 증가함에 따라 가장 작은 빌딩을 어디에 놓는지가 핵심인 문제이다.

 

1. 가장 작은 빌딩을 맨 왼쪽에 넣는다. => D[N-1][L-1][R] 

2. 가장 작은 빌딩을 맨 오른쪽에 넣는다 => D[N-1][L][R-1]

3. 가장 작은 빌딩을 중간에 넣는다ㅏ. => D[N-1][L][R]*(N-2) 

 

3번에서 N-2번 곱한 이유는 왼쪽과 오른쪽을 제외하면 나머지 넣을 수 있는 경우의 수가 N-2번이기 때문에 곱해줘야 된다.

 

 

 

[소스코드]

 

#include <iostream>
#include <vector>
#include <cstring>
#include <string.h>
using namespace std;

long mod = 1000000007;

long D[101][101][101];
int N, L, R;

int main(void) {
	cin >> N >> L >> R;

	D[1][1][1] = 1;

	for (int i = 2; i <= N; i++) {
		for (int k = 1; k <= L; k++) {
			for (int j = 1; j <= R; j++) {
				D[i][k][j] =
					D[i - 1][k][j] * (i - 2) +
					D[i - 1][k][j - 1] +
					D[i - 1][k - 1][j];
				D[i][k][j] %= mod;
			}
		}
	}
	cout << D[N][L][R];
}