[백준 1328] 고층 빌딩

문제 출처 : https://www.acmicpc.net/problem/1328

1328번: 고층 빌딩

문제 이해하기

빌딩을 왼쪽에서 보았을 때, 오른쪽에서 보았을 때를 가지고 빌딩의 순서를 출력하는 문제 입니다. 어려운 문제이지만 차근차근 생각하면 해결할 수 있습니다. 이 문제를 풀 때에는 모든 빌딩이 바닥에서부터 쏟아오른다고 생각하면 좀 더 쉽습니다.

문제의 예로 나온 N = 5, L = 3, R = 2를 생각해 보겠습니다. 총 5개의 건물이 있고 왼쪽에서는 3개의 빌딩이 보이고, 오른쪽에서는 2개의 빌딩이 보입니다. 이 빌딩이 지하로 가라앉아 있다가 올라오고 있다고 생각하겠습니다.

먼저 건물이 1만큼 위로 올라왔을때를 생각해 보겠습니다.

1만큼 올라왔기 때문에 위와 같은 모습이 되었을 것입니다. 이는 N = 1, L = 1, R = 1과 같습니다. 이 경우의 수는 한가지 밖에 없습니다. 따라서 이것을 다음과 같이 표시할 수 있습니다.

dp[n][l][r] = dp[1][1][1] = 1

이제 건물이 1 만큼 더 올라왔습니다. 그럼 다음과 같이 두 가지 경우가 생깁니다.

원래 1이였던 건물은 2의 높이가 됩니다. 그리고 1의 건물이 앞쪽에 위치하거나, 뒤쪽에 위치하는 경우가 있습니다. 앞의 배열은 N = 2, L = 2, R = 1이 되고, 뒤의 배열은 N = 2, L = 1, R = 2가 됩니다.

이제 또 하나의 건물이 올라온다고 생각하겠습니다. 상단에서 앞쪽인 N = 2, L = 2, R = 1의 경우만 따져보면 아래와 같이 3가지가 나옵니다.

첫 번째는 N = 3, L = 3, R = 1 이고, 두 번째는 N = 3, L = 2, R = 1, 마지막 세 번째는 N = 3, L = 2, R = 2 입니다. 결국 빌딩이 1씩 올라갈 때에는 앞쪽에서 올라오던가, 뒤쪽에서 올라오던가, 중간에서 올라오던가 3가지 경우 중 하나 입니다. 즉 N = 5, L = 3, R = 2 인 경우는 N = 4, L = 2, R = 2 에서 앞에서 올라온 경우와, N = 4, L = 3, R = 1 에서 뒤에서 올라온 경우, 그리고 N = 4, L = 3, R = 2에서 중간에서 올라온 경우 입니다. 앞과 뒤에서 올라온 경우는 1가지씩 밖에 없으니 문제가 안되지만 가운데서 올라온 경우는 문제가 생깁니다.

1, 2, 3번중 어디에서 올라와도 상관이 없기 때문입니다. 맨 앞과 뒤는 빼고 생각해야 합니다. N = 5가 되기 때문에 총 5군데에 1짜리 빌딩을 세울 수 있지만 이미 앞과 뒤를 제외한 가운데만 체크하기 때문에 3군데에 올릴 수 있는 것입니다. 즉 N의 갯수에서 앞과 뒤를 뺀 N - 2 만큼을 세울 수 있는 것이고, 중간의 경우의 수는 N - 2만큼 생기는 것입니다. N = 4, L = 3, R = 2의 경우의 수가 3가지라면 1이 올라왔을 때 3가지, 2가 올라왔을 때 3가지, 3이 올라왔을 때 3가지로 총 9개의 경우의 수가 생기는 것입니다.

그럼 아래와 같은 점화식을 만들 수 있습니다.

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

이 점화식을 통해 코드를 작성해 보겠습니다.

코드 작성

입력 받기

N, L, R = map(int, input().split())

총 빌딩의 수 N과 왼쪽에서 보이는 빌딩의 수 L, 오른쪽에서 보이는 빌딩의 수 R을 입력 받습니다.

출력 하기

MOD = 10 ** 9 + 7
dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]

solve(N, L, R)
print(dp[N][L][R])

문제에서 숫자가 너무 커질 수 있기 때문에 1,000,000,007 로 나눈 나머지를 출력하라고 합니다. 따라서 이 숫자를 MOD 값으로 만들어 줍니다.

다이나믹 프로그래밍한 결과를 저장할 dp 리스트를 만들어 줍니다. N, L, R 세개의 값을 가지고 있기 때문에 3차 리스트로 생성 합니다. dp[n][l][r] 에는 빌딩의 경우의 수가 저장되어 있습니다.

solve 함수를 통해 결과를 dp에 저장합니다. 마지막으로 dp[N][L][R]값을 출력하면 결과를 얻을 수 있습니다.

solve 함수

def solve(n, l, r):
    dp[1][1][1] = 1

    for i in range(2, N + 1):
        dp[i][i][1] = dp[i][1][i] = 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)) % MOD

solve 함수 입니다. 먼저 N이 1일 때는 L과 R 모두 1 입니다. 이 경우의 수는 1밖에 없기 때문에 초기값으로 생성해 줍니다. 다음으로 빌딩의 높이 N을 생각해보겠습니다. 맨 앞과 맨 뒤에 하나씩 올라오는 경우는 한가지밖에 존재하지 않습니다. 따라서 dp[i][i][1]과 dp[i][1][i] 값은 무조건 1이 됩니다.

다음으로 L과 R에 따라서 bottom up 형태로 값을 만들어 줍니다. dp[i][j][k] 값은 먼저 맨 앞에 한 칸 올라올 경우를 생각합니다. dp[i - 1][j - 1][k]이 맨 앞에 1이 올라오는 경우 이고 dp[i - 1][j][k - 1]이 맨 뒤쪽에 1이 올라오는 경우 입니다.

중간은 dp[i - 1][j][k] 입니다. 여기에 빌딩이 올라올 수 있는 자리는 (i - 2)개 있기 때문에 (i - 2)를 곱해주어 경우의 수를 늘려줍니다. 마지막으로 저장하기 전에 숫자가 너무 커지기 때문에 MOD 값으로 나머지 연산하여 숫자를 줄여줍니다.

최종적으로 dp[N][L][R]을 보면 빌딩의 경우의 수를 알 수 있습니다.

전체 코드

전체 코드를 확인해 보겠습니다.

N, L, R = map(int, input().split())
MOD = 10 ** 9 + 7

dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]

def solve(n, l, r):
    dp[1][1][1] = 1

    for i in range(2, N + 1):
        dp[i][i][1] = dp[i][1][i] = 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)) % MOD

solve(N, L, R)
print(dp[N][L][R])