[백준] No.1328 - 고층 빌딩 (C++)

문제

https://www.acmicpc.net/problem/1328

1328번: 고층 빌딩

 

풀이

난이도: Gold 1

 

곰곰이 생각해보아도 점화식이나 재귀 함수로도 구현이 잘 되지 않아 풀기 힘들었다.

해결 풀이는 재미지님의 징검다리 블로그 게시물을 참조하였다.

 

[ BOJ 백준 1328번 - 고층 빌딩 ] 해설 및 코드 - 징검다리

 

빌딩은 N개이며 같은 높이를 가지지 않기 때문에 1~N의 높이를 가진다.

 

3차원 배열을 선언하여

dp[idx][l][r]에 idx번째 수(큰 수부터 내림차순으로) 배치시켰을 때, 왼쪽에서 보이는 빌딩 수 l, 오른쪽에서 보이는 빌딩 수 r인 경우의 가능한 빌딩 순서를 저장하자.

 

idx는 큰 수부터 시작하기 때문에 현재의 수는 1~idx-1보다 작은 수이다.

따라서 아래의 3가지 경우로 분기한다.

 

1. 가장 왼쪽에 배치하는 경우

 배치된 수 중에서 가장 작기 때문에 l(왼쪽에서 보이는 빌딩 수)만이 +1 증가한다.

 idx-1번째 수까지 배치되고, l-1,r인 경우에서 idx가 왼쪽에 배치되므로 (l-1)+1이 된 dp[idx-1][l-1][r]의 값을 사용한다. 

 

2. 가장 오른쪽에 배치하는 경우

 r(오른쪽에서 보이는 빌딩 수)만이 +1 증가한다.

 동일한 이유로 dp[idx-1][l][r-1]의 값을 사용한다. 

 

3.  왼쪽과 오른쪽을 제외한 모든 곳에 배치한다.

 가장 작은 수이기 때문에 왼쪽과 오른쪽을 제외한 어느 위치에 배치되더라도 l,r의 값에 변화를 주지않는다.

 dp[idx-1][l-1][r-1]의 값에 idx-1개의 빌딩 사이의 개수 idx-2를 곱한 값을 사용한다.

dp[idx-1][l][r]*(idx-2)

 

 

따라서 점화식은 아래와 같다.

dp[idx][l][r] = dp[idx-1][l-1][r] + dp[idx-1][l][r-1] + dp[idx-1][l][r]*(idx-2)

 

코드 구현 시 mod가 적용된 dp[idx-1][l][r] 값에 (idx-2)를 곱하면 int형의 범위를 초과할 수 있기 때문에 long long 형을 사용해주자.

 

이와 동일한 문제로 [백준] 막대 배치(8895)도 존재한다.

 

 

코드