백준 1328번 고층 빌딩

< 백준 1328번 고층 빌딩 - 마포 코딩박 >

사용한 알고리즘: DP


 일렬로 늘어선 N개의 빌딩을 왼쪽(Left), 오른쪽(Right)에서 본 결과를 입력으로 받고, 가능한 배열의 수를 찾는 문제였습니다. DP를 사용하여 해결하였습니다. 풀이를 바로 생각하기 어려운 문제였습니다.

문제풀이는 다음과 같습니다.

(1) N개의 빌딩이 있을때, Left=1&&Right=N 이거나 정반대의 경우, 가능한 배열 수는 1 ( 유일 ) 입니다.

(2) N 개의 빌딩 배열은 N-1 개의 빌딩 배열에서 오는 것을 생각합니다.

(3) N-1 개 빌딩 배열로 -> N 개 빌딩 배열을 만든다고 생각할 때,
    큰 빌딩 1개를 추가한다고 생각하면 헷갈리므로,
    " N-1 개의 빌딩의 높이를 1씩 높여준 뒤, 높이 1 의 제일 작은 빌딩을 추가한다 " 
    라고 생각합니다.

(4) 위의 생각에서, N-1 개의 빌딩에 작은빌딩 1개를 추가로 배열 할 수 있는 위치 수는 N개 입니다.

(5) N-1개의 빌딩 양 끝에 작은 빌딩을 세우면 Left+1 or Right+1 이 됩니다. ( 2자리)
이를 제외한 모든 위치에 작은빌딩을 추가하는 것은 Left와 Right 에 변화를 줄 수 없습니다. ( N-2 자리)

(6) 위의 생각을 제귀함수로 구현하고, 이 과정에서 dp 를 활용해 저장합니다. ( 16번째 줄: 이미 완성된 배열일 경우 return 으로 중복해서 확인하는걸 줄여줘야 시간내에 돌릴 수 있습니다. )

위의 빨간색으로 강조한 생각을 하는 것이 힘들었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	// 작은 빌딩을 넣는다고 생각
	const int MOD = 1000000007;
	const int MAX = 102;
	typedef long long ll;
	int N, L, R;
	ll dp[MAX][MAX][MAX];
	ll CountingNum(int building, int Left, int Right){
	// 기저
	if((Left==1&&Right==building)||(Left==building&&Right==1)) return 1LL;
	// 불가능한 경우
	if(building==0||Left==0||Right==0) return 0LL;
	ll &ret = dp[building][Left][Right];
	// 이미 아는 값이면 return
	if(ret!=-1) return ret;
	// 넣을 수 있는 자리
	int place = building-2;
	ret = (CountingNum(building-1,Left,Right)*place+CountingNum(building-1,Left-1,Right)+CountingNum(building-1,Left,Right-1))%MOD;
	return ret;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> L >> R;
	memset(dp,-1,sizeof(dp));
	cout << CountingNum(N,L,R)%MOD << '\n';
	return 0;
	}

view raw BOJ 1328.cpp hosted with ❤ by GitHub