1328 고층 빌딩

문제

문제는 아래 링크에서 확인
BOJ 1328 고층빌딩

문제 풀이

이 문제에서 사용되는 알고리즘은 다이나믹 프로그래밍이다. 핵심 점화식은

1

D[i][j][k] = (D[i-1][j][k-1] + D[i-1][j-1][k] + (i-2)*D[i-1][j][k]) %Mod

이다.

하나씩 뜯어서 보자.

• D[i][j][k]의 의미

D[i][j][k] = i개의 건물이 있을 때, 왼쪽에서 j개의 건물이 보이고 오른쪽에서 k개의 건물이 보이는 경우의 수

• D[i-1][j][k-1]를 더하는 이유

i-1개의 건물이 있을 때, j개의 건물이 왼쪽에서 보이고 오른쪽에서 봤을 때, k-1개의 건물이 보이는 상황을 상상해봅시다.

이때, i-1개의 건물들보다 작은 어떤 한 건물이 맨 오른쪽에 추가됬다고 합시다.

그러면 왼쪽에서 볼 때는 어차피 안보이기 때문에 j개 그대로 보입니다.

반면에 오른쪽에서 볼 때는 제일 작은 i번째 건물이 새로 추가되어 보이기 때문에 k개의 건물이 보이게 됩니다.

따라서, D[i-1][j][k-1]은 D[i][j][k]에 포함됩니다.

• D[i-1][j-1][k]

위와 비슷합니다.

이번엔 오른쪽이 아닌 왼쪽에 제일 작은 건물 하나가 추가된다고 생각하면 됩니다.

• (i-2) * D[i-1][j][k]

위의 2가지 경우로 제일 작은 i번째 건물이 맨 왼쪽, 오른쪽에 추가되는 경우가 나왔습니다.

그러면 당연히 이제 중간에 추가되는 경우입니다.

i-2는 추가될 수 있는 위치의 개수입니다.

(i-1개의 건물이 있을 떄, i-2 곳에 건물을 배치할 수 있습니다.)

그러면 이제 왜 건물을 중간에 위치하는데 D[i-1][j][k]를 곱하느냐만 알면 됩니다.

한번 제일 작은 건물을 추가한다는 것에 집중해봅시다.

제일 작은 건물을 기존 건물들 사이에 집어넣은다고 생각하면,

어차피 제일 작은 건물은 기존 건물들에 가려져 안보입니다.

따라서, 제일 작은 건물을 추가해도 당연히 왼쪽, 오른쪽에서 보이는 건물의 개수가 변하지 않기 때문에 (i-2)에 D[i-1][k][k]를 곱하면 된다는 얘기가 됩니다.

문제 코드

python

1
2
3
4
5
6
7
8
9

D = [[[0]*110 for i in range(110)] for j in range(110)]
N,L,R = map(int,input().split())
D[1][1][1] = 1
Mod = 1000000007
for i in range(2,N+1):
    for j in range(1,L+1):
        for k in range(1,R+1):
            D[i][j][k] = (D[i-1][j][k-1] + D[i-1][j-1][k] + (i-2)*D[i-1][j][k]) %Mod
print(D[N][L][R])

오늘의 잡소리

처음에 이 문제를 봤을 때, 이걸 어떻게 풀지라는 생각을 했고 고민을 좀 많이 했습니다.

살짝의 힌트를 얻으려고 다른 분들의 풀이를 살짝만 보자하고 봤었습니다.

문제는 풀이가 되게 짧았고 그게 바로 핵심이었고 강렬한 스포를 당해 문제를 푸는 것이 싱겁게 되었습니다..ㅋㅋㅋ