[ 백준 ] 1328 고층 빌딩 ( Python )

게시 2024/06/16

By KimJinwoo 7 분읽는 시간

BOJ 1328

고층 빌딩 문제 풀이

안녕하세요! 오늘은 백준 알고리즘 문제 중 하나인 “고층 빌딩” 문제에 대해 알아보도록 하겠습니다.

문제 접근 방법

이 문제는 Dynamic Programming(DP)을 활용하여 해결할 수 있습니다. DP는 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 활용하여 전체 문제를 해결하는 알고리즘입니다.

문제에서 주어진 조건은 다음과 같습니다:

빌딩의 개수 N
가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L
가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R

우리는 이 조건을 만족하는 빌딩 배치의 경우의 수를 구해야 합니다.

DP 점화식 도출 과정

먼저, DP 배열의 정의를 명확히 해야 합니다. 여기서는 dp[i][j][k]를 “i개의 빌딩이 있고, 왼쪽에서 j개, 오른쪽에서 k개의 빌딩이 보이는 경우의 수”로 정의합니다.

이제 점화식을 세우기 위해, i번째 빌딩을 추가할 때 고려해야 할 사항을 생각해봅시다.

새로 추가된 i번째 빌딩이 가장 높은 경우:
- 이 경우, 왼쪽에서 보이는 빌딩의 수가 1 증가합니다.
- 따라서 dp[i][j][k]는 dp[i-1][j-1][k]와 같습니다.
새로 추가된 i번째 빌딩이 가장 낮은 경우:
- 이 경우, 오른쪽에서 보이는 빌딩의 수가 1 증가합니다.
- 따라서 dp[i][j][k]는 dp[i-1][j][k-1]와 같습니다.
새로 추가된 i번째 빌딩이 중간 높이인 경우:
- 이 경우, 왼쪽과 오른쪽에서 보이는 빌딩의 수는 변화가 없습니다.
- 하지만 i번째 빌딩이 들어갈 수 있는 위치의 수를 고려해야 합니다.
- i번째 빌딩은 1번째부터 (i-1)번째까지의 빌딩 사이에 들어갈 수 있습니다.
- 따라서 dp[i][j][k]는 dp[i-1][j][k] * (i-2)와 같습니다.

위의 세 가지 경우를 모두 더하면 i번째 빌딩을 추가했을 때의 경우의 수를 구할 수 있습니다.

dp[i][j][k] = dp[i-1][j-1][k] + dp[i-1][j][k-1] + dp[i-1][j][k] * (i-2)

이것이 바로 이 문제의 DP 점화식입니다.

풀이 과정

3차원 DP 배열을 생성하고 초기값을 설정합니다.
- dp[1][1][1] = 1 (빌딩이 1개일 때, 왼쪽과 오른쪽에서 모두 1개의 빌딩이 보이는 경우는 1가지)
빌딩의 개수 i를 2부터 N까지 순회하면서 DP 값을 갱신합니다.
- 점화식에 따라 dp[i][j][k]의 값을 계산합니다.
- 계산 시 모듈러 연산을 적용하여 결과를 1,000,000,007로 나눈 나머지를 저장합니다.
최종적으로 dp[N][L][R]의 값이 문제의 정답이 됩니다.

시간 및 공간 복잡도 분석

시간 복잡도: O(N^3)
- 3중 반복문으로 인해 N^3의 시간 복잡도를 가집니다.
공간 복잡도: O(N^3)
- 3차원 DP 배열을 사용하므로 N^3의 공간 복잡도를 가집니다.

시행착오 및 어려움

처음에는 단순히 순열을 활용하여 모든 경우를 탐색하려고 했습니다. 하지만 이는 시간 복잡도가 팩토리얼 수준으로 매우 높아 시간 초과가 발생할 것임을 알 수 있었습니다.

DP를 활용하는 아이디어를 떠올리는 것도 쉽지 않았습니다. 특히 점화식을 세우는 과정에서 i번째 빌딩이 중간에 위치하는 경우를 고려하는 것이 어려웠습니다.

하지만 문제의 조건을 잘 분석하고, 부분 문제를 정의하는 과정에서 아이디어를 얻을 수 있었습니다. 또한 점화식을 세우는 과정을 꼼꼼히 따라가며 논리를 정립할 수 있었습니다.

DP 문제를 접할 때는 항상 “큰 문제를 작은 문제로 나눌 수 있는가”, “중복 계산이 발생하는가”를 고민해보는 것이 좋습니다. 그리고 부분 문제의 정의와 점화식을 명확히 세우는 것이 중요합니다.

전체 코드 보기

  
import sys
input = sys.stdin.readline
n, l, r = map(int, input().split())
num = 1000000007
dp = [[[0] * (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 문제 풀이에 도움이 되셨기를 바랍니다. 감사합니다!

문제풀이, 알고리즘