[백준 1328번] 고층 빌딩 (java)

1328번: 고층 빌딩

 

다이나믹 프로그래밍으로 해결할 수 있다.

 

dp[n][l][r] : n번째 빌딩을 세울 때, 왼쪽에서 보이는 빌딩의 수가 l개, 오른쪽에서 보이는 빌딩의 수가 r개가

되도록 건물을 배치하는 모든 경우의 수

 

 

먼저, 처음으로 빌딩을 하나 세웠다고 치자.

건물이 하나밖에 없으므로 왼쪽에서 보이는 건물의 수는 1개, 오른쪽에서 보이는 건물의 수도 1개가 된다.

-> dp[1][1][1] = 1

 

그 다음으로 두번째 빌딩을 하나 세운다.

그러면 두 가지 중 하나이다. 왼쪽에서 보이는 건물의 수가 2개이고 오른쪽에서 보이는 건물의 수가 1개이거나, 혹은 왼쪽에서 보이는 건물의 수가 1개이고 오른쪽에서 보이는 건물의 수가 2개인 경우.

-> 즉, dp[2][2][1] = dp[2][1][2] = 1 이다.

 

이번에는 4번째로 빌딩을 세운다고 하자.

만약 네번째 빌딩을 세움으로써 왼쪽에서 보이는 건물이 2개, 오른쪽에서 보이는 건물이 2개가 될 때의 경우의 수(dp[4][2][2])를 구한다고 하면, 어떤 방법이 있을까?

 

가장 왼쪽에 빌딩 추가하기

아래 그림의 왼쪽의 경우는 dp[3][1][2]이다. 

3개의 빌딩을 세웠을 때, 왼쪽에서 보이는 빌딩의 개수는 1개, 오른쪽에서 보이는 빌딩의 개수는 2개이다.

이 상태에서 가장 왼쪽에 높이 1 짜리 빌딩을 세우면, 왼쪽에서 보이는 빌딩 2개, 오른쪽에서 보이는 빌딩 2개가 된다. -> dp[4][2][2]

 

 

가장 오른쪽에 빌딩 추가하기

아래의 왼쪽 그림을 보면, 왼쪽에서 보이는 빌딩의 개수는 2개, 오른쪽에서 보이는 빌딩의 개수는 1개로, dp[3][2][1]에 속하는 경우이다.

여기서 가장 오른쪽에 높이가 3인 네번째 빌딩을 추가하면 왼쪽에서 보이는 건물은 2개, 오른쪽에서 

보이는 건물도 2개가 된다. -> dp[4][2][2]

 

중간에 빌딩 추가하기

혹은 기존의 3개의 빌딩 사이사이에 네번째 빌딩을 추가할 수도 있다.

아래의 첫번째 그림을 보면, 네번째 빌딩을 두번째 위치에 추가함으로써 왼쪽에서 보이는 빌딩 개수 2개,

오른쪽에서 보이는 빌딩 개수 2개를 만들 수 있다. -> dp[4][2][2]

 

네번째 빌딩을 세번째 위치에 추가하여 왼쪽에서 보이는 빌딩 개수 2개,

오른쪽에서 보이는 빌딩 개수 2개를 만들 수 있다. -> dp[4][2][2]

 

 

 

위의 예제로부터 알 수 있는 사실이 있다.

n개의 건물을 세웠을 때,

왼쪽에서 보이는 빌딩의 개수가 l개, 오른쪽에서 보이는 빌딩의 개수가 r개가 되려면.

즉, dp[n][l][r]가 되는 경우의 수를 구하려면, 

 

다음과 같이 3가지가 있다.

 

1. n-1개의 건물을 세웠을 때, 왼쪽에서 보이는 빌딩의 개수가 (l-1)개, 오른쪽에서 보이는 빌딩의 개수가

   r개인 상태(dp[n-1][l-1][r])에서 가장 왼쪽에 n번째 빌딩을 세우는 경우

 

2. n-1개의 건물을 세웠을 때, 왼쪽에서 보이는 빌딩 개수가 l개, 오른쪽에서 보이는 빌딩 개수가 (r-1)개인

   상태(dp[n-1][l][r-1])에서 가장 오른쪽에 n번째 빌딩을 세우는 경우

 

3. n-1개의 건물을 세워을 때, 왼쪽에서 보이는 빌딩 개수가 l개, 오른쪽에서 보이는 빌딩 개수가 r개인 

   상태(dp[n-1][l][r])에서 중간에 n번째 빌딩을 세우는 경우

   이 때, 중간에 세울 수 있는 경우의 수는 양 끝을 제외한 (n-2)가지가 있다.

 

 

이를 바탕으로 점화식을 세우면,

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

 

전체 코드 :