문제 정보
- 문제 번호 : 1328
- 문제 이름 : 고층 빌딩
- 문제 링크 : https://www.acmicpc.net/problem/1328
- 정답 코드 : https://github.com/dalmengs/algorithm-solutions/blob/main/1328/main.py
- 난이도 : Platinum 5
- 체감 난이도 : Gold 1
- 알고리즘 : DP
문제 설명
높이가 1, 2, … N로 서로 다른 N개의 빌딩이 있다고 하자.
빌딩의 개수, 왼쪽에서 본 빌딩의 개수, 오른쪽에서 본 빌딩의 개수가 주어질 때, 가능한 빌딩 순서의 경우의 수를 구하는 문제이다.
문제 해결
N이 최대 100이므로 보자마자 DP 배열을 dp[N][left][right]로 세웠다.
다른 DP 문제처럼 i번째 빌딩이 추가될 때를 가정하고 이전 상태를 통해 현재 상태를 업데이트 하기로 했고, 그 방법을 생각해보았는데, 생각보다 쉽게 떠오르지 않았다.
아무리 생각해도 이 방향이 맞는 거 같는데, 해답이 떠오르지 않을 때는 반대로 추가하는 것을 고려해봐야 한다.
높이가 i인 i번째 빌딩을 추가하는 것이 아닌, 높이가 1인 빌딩을 추가하여 이전의 상태를 [1, i - 1]에서 [2, i]로 간주하는 방식으로 생각했더니 매우 쉽게 문제가 풀렸다.
빌딩의 높이를 1씩 올려도 보이는 위치 관계는 변하지 않기 때문에 문제가 없었다.
즉, 가장 작은 빌딩을 i - 1개의 빌딩에 끼워넣으면 되는 문제이다.
가장 작은 빌딩이 왼쪽에 있는 경우에는 왼쪽에서 보이는 빌딩의 개수가 하나 더 늘어난 것이다.
이 경우, dp[i][left][right] = dp[i - 1][left - 1][right]로 구할 수 있다.
가장 작은 빌딩이 오른쪽에 있는 경우에는 오른쪽에서 보이는 빌딩의 개수가 하나 더 늘어난 것이다.
이 경우, dp[i][left][right] = dp[i - 1][left][right - 1]로 구할 수 있다.
나머지는 빌딩이 중간에 놓이는 경우인데, 이때는 보이는 빌딩의 개수는 변하지 않고, 이 빌딩을 놓을 수 있는 위치는 i개의 위치 중 왼쪽과 오른쪽을 제외한 i - 2개이다.
이 경우, dp[i][left][right] = dp[i - 1][left][right] * (i - 2)로 구할 수 있다.
정답 코드
MOD = int(1e9 + 7)
n, l, r = map(int, input().split())
dp = [[[0 for _ in range(r + 1)] for _ in range(l + 1)] for _ in range(n + 1)]
dp[1][1][1] = 1
for i in range(2, n + 1):
for left in range(1, i + 1):
for right in range(1, i + 1):
if left > l or right > r: break
dp[i][left][right] = (
dp[i][left][right] +
dp[i - 1][left - 1][right] +
dp[i - 1][left][right - 1] +
dp[i - 1][left][right] * (i - 2)
) % MOD
print(dp[n][l][r])마무리
정말 좋은 문제라고 생각한다.
쓸데 없는 함정도 없고, 아이디어만 떠올리면 매우 간단한 코드로 풀린다.
매번 가장 낮은 빌딩이 추가되는 걸로 발상을 전환하는 것이 매우 중요한 문제였다.
비단 이 문제 뿐만 아니라, 방향은 맞는 거 같은데 아무리 생각해봐도 풀이가 진행되지 않으면 반대로 생각해보는 습관을 들여야겠다.
댓글 남기기