[Python] 1328 - 고층 빌딩 (플래티넘5)

1. 문제 설명

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

1328번: 고층 빌딩

dp문제는 웬만하면 이제 풀이 방법이 너무 뻔히 보인다고 해야 하나..

플래티넘치고는 쉬웠다.

 

---

2. 아이디어

생각이 안 떠오를 땐 노가다라도 해라.

DP문제일 거라는 생각은 들었는데 인덱스에 어떤 조건을 넣어줄까 생각해보니

왼쪽에서 보는 경우, 오른쪽에서 보는 경우는 필수로 들어가야 할 것 같고

패턴을 찾아보다보니 빌딩의 높이도 고려해줄 필요가 있음을 느꼈다.

정확하게는 dp[빌딩 수(= 최대 높이)][왼쪽에서 보이는 개수][오른쪽에서 보이는 개수]였다.

 

이 문제는 높이가 1인 경우부터 거슬러 올라가며 N까지 모든 경우의 수를 찾아야 한다.

노가다를 해도 어느정도 보이긴 하는데 워낙 경우가 많다보니..미치기 딱 좋다. 조금 다른 접근법이 필요하다.

 

N이 4일 때, 아무 경우나 하나 그려보자.

그리고 N이 5인 경우일 때 예시를 하나 그려보라고 하면 어떻게 하겠는가?

그림을 다 지우기 보다는 이미 그려진 그림에 블럭을 한 칸씩 더 쌓고 빈 공간에 블럭 하나를 추가할 것이다.

이게 바로 핵심이다.

 

모든 블럭에 한 칸씩 쌓아올리면(아직 1칸짜리를 놓지 않음) 높이가 4일 때나 5일 때나

좌/우에서 각각 2개씩 보이는 것은 똑같다.

결국 1칸짜리 블럭을 어디 놓을 것이냐가 분기점을 좌우하게 된다.

가장 왼쪽에 놓으면 [height + 1][left + 1][right]가 될 것이고, 오른쪽이면 [height + 1][left][right + 1]인 경우일 것이다.

그런데 블럭들 사이에 숨겨버리면? [height + 1][left][right] * (사이 공간 수)가 되어버린다.

 

그 경우를 모두 계산하고 원하는 케이스의 경우의 수를 출력하면 해결할 수 있다.

 

---

3. 코드

def solution():
    n, l, r = map(int, input().split())
    
    legend = [[[0]*101 for _ in range(101)] for _ in range(101)]
    legend[1][1][1] = 1

    for height in range(2, n+1):
        for left in range(1, l+1):
            for right in range(1, r+1):
                legend[height][left][right] = (legend[height-1][left][right-1] + legend[height-1][left-1][right] + (legend[height-1][left][right])*(height-2)) % 1000000007
    print(legend[n][l][r])

solution()

변수명이 legend인 이유는 당시 이 아이디어를 떠올린 내가 legend라는 이유였던 거 같다. ㅎㅎ