[백준/BOJ] platinum5 - 1328번 고층 빌딩 (Python)

▶1328 - 고층 빌딩

▶문제

상근이가 살고 있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다.

상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다.

빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오.

예를 들어, N = 5, L = 3, R = 2인 경우에 가능한 빌딩의 배치 중 하나는 1 3 5 2 4이다.

 

▶입력

첫째 줄에 빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어진다.

 

▶출력

첫째 줄에 가능한 빌딩 순서의 경우의 수를 1000000007로 나눈 나머지를 출력한다.

 

▶예제

 

▶풀이

이번 문제는 생각을 많이 했던 문제인 것 같다.

dp의 기본이 bottom-up방식인 것을 생각해보면 간단하게 해결됐던 거 같다.

건물을 1개가 있을 때부터 n개가 있을 때까지 점차적으로 증가시켰다.

 

dp[n][l][r]은 n개의 건물, 좌측엔 l개, 우측엔 r개가 있는 경우이다.

그리고 n, l, r 중 하나가 0일 땐 무조건 0이 된다. (조건이 성립 X)

 

건물이 1개가 있을 때는 좌우측에서 1개씩 보인다

따라서 dp[1][1][1] = 1이 된다.

 

이것을 토대로 점차 비교해보면

dp[2][2][1]은 dp[1][1][1]에서 건물이 하나 추가되는데 좌측에서 하나가 더 보이는 경우이다.

dp[2][1][2]은 dp[1][1][1]에서 건물이 하나 추가되는데 우측에서 하나가 더 보이는 경우이다.

 

이런 규칙을 통해서 조금 더 큰 값을 생각해보았다.

예제는 dp[5][3][2]를 구해야 한다.

이 값은 총 세 가지의 경우를 더하면 된다.

 

dp[4][2][2]에서 가장 좌측에 빌딩이 하나 추가되어서 좌측에서 보이는 빌딩이 하나가 추가된 경우

dp[4][3][1]에서 가장 우측에 빌딩이 하나 추가되어서 우측에서 보이는 빌딩이 하나가 추가된 경우

dp[4][3][2]에서 빌딩이 추가되는데 양 끝에 추가되는 경우가 아니라 사이에 추가되는 경우이다.

사이에 추가되는 경우는 좌우측에서 보이는 빌딩수의 차이가 없다. 

l, r이 3, 2로 유지되고 들어갈 수 있는 경우는 들어갈 수 있는 경우 5중에서 양끝을 뺀 3가지이다.

따라서 dp[5][3][2] = dp[4][2][2] + dp[4][3][1] + dp[4][3][2] * 3이 된다.

 

이것을 바탕으로 n, l, r로 간단한 식을 적어보면

dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + dp[n-1][l][r] * (n-3)이 된다.

이렇게 풀이를 적어서 제출하니 정답이 나왔다. 

 

첫 번째 반복문은 2부터 시작한다.

나머지 사이사이 쓸데없는 경우는 값이 0이 된다.

n, l, r = map(int, input().split())
num = 1000000007
dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[1][1][1] = 1
for i in range(2, n+1):
    for j in range(1, l+1):
        for k in range(1, r+1):
            dp[i][j][k] = (dp[i-1][j-1][k] + dp[i-1][j][k-1]
                           + dp[i-1][j][k] * (i - 2)) % num

print(dp[n][l][r])

dp문제치고는 생각보다 까다로웠던 것 같다. 역시 플레 문제는 플레 문제다.

설명을 적으면서도 제대로 적고 있는지는 잘 모르겠다.

하지만 코드를 보고 문제를 이해하려고 한다면 충분히 이해할 수 있을 것이다.

 

그리고 생각해내는 과정과, 고민했던 시간들에 비하면 코드의 길이는 너무 짧은 것 같다.

그리도 또 하나의 플레 문제 해결했으니 만족한다.

 

solved.ac도 이제 platinum5까지 108점 남았다. 이번 방학 끝날 때까지 플레 찍어보자!