은비는 길을 걷다가 관광 명소인 쌍둥이 빌딩 숲을 보게 되었습니다. 쌍둥이 빌딩 숲은 일렬로 빌딩들이 줄지어 서있는 곳입니다. 쌍둥이 빌딩 숲에는 높이가 1부터 n까지 각각 2 채씩 총 2n채의 빌딩이 존재하기 때문에 그러한 이름이 붙게 되었으며, 같은 높이를 가지는 빌딩 사이에는 그보다 높은 빌딩이 존재하지 않습니다.
은비는 쌍둥이 빌딩 숲을 한쪽 측면에서(열 방향으로) 바라보고 있습니다. 이때 count 채의 빌딩이 구분되어 보였습니다.
은비의 세계는 안타깝게도 원근감이 존재하지 않지만, 다행히 서로 다른 높이를 가지는 빌딩들은 각각 고유한 색깔을 가지고 있어 어떤 빌딩이 다른 빌딩에 의해 전체가 가려지지 않는다면 볼 수 있습니다.
예를 들어 은비가 바라본 방향에서 가까운 빌딩부터 차례로 높이가 1,1,3,2,2,3 순이라면 높이가 2인 빌딩은 가려져서 보이지 않고, 높이가 1인 빌딩과 높이가 3인 빌딩만 구분되어 보입니다.
n과 count가 주어졌을 때, 빌딩들이 배치될 수 있는 방법의 수를 return 하도록 solution 함수를 완성해주세요.
결과는 매우 클 수 있으므로 1,000,000,007 로 나눈 나머지를 return합니다.
입출력 예
n
count
result
3
1
8
3
2
6
3
3
1
풀이
DP 문제. 접근을 조금 꼬아서 생각해보아야 한다.
빌딩을 낮은 순서부터 차례로 배치하기보다, 높은 순서로 배치하는 게 훨씬 더 고려해야 할 경우의 수가 줄어든다. (i, j)인 경우를 생각해 보자. 이는 총 i개 높이의 빌딩을 조건에 맞추어 배치했을 때, 앞에서 바라보면 j개가 보이는 경우의 수를 의미한다. 여기서 이들보다 작은 빌딩 2개를 배치한다고 가정하자. (i, j)는 총 2i개의 빌딩 길이를 가지며, 2i+1개의 빌딩 사이의 틈이 존재한다.
(i + 1, j + 1) : (i, j)로 배치한 빌딩들 바로 앞에 새로 빌딩을 하나 추가하는 경우의 수다. 빌딩은 같이 붙어 있어야 한다. (떨어져 있을 경우, 같은 높이를 가지는 빌딩 사이에는 그보다 높은 빌딩이 존재하지 않는다는 조건에 위배된다) 즉 (i, j)를 그대로 더해줄 수 있다.
(i + 1, j) : (i+1, j+1)로 배치된 빌딩을 제외한 나머지 경우의 수가 된다. 즉 (i, j)*2i 를 더해 줄 수 있다.
이를 (i, j)에 대한 점화식으로 나타내 보면 다음과 같아진다.
DP( i , j ) = DP( i - 1, j - 1 ) + DP( i - 1, j ) * ( 2i - 2 )
혹은 위에 설명한 대로 구현해도 되며, 나는 위의 방식으로 풀이하였다.
풀이 코드
MAX = 1000000007
def solution(n, count):
dp = [[0]*(n+1) for _ in range(n+1)]
dp[1][1] = 1
for i in range(1, n):
for j in range(1, i+1):
dp[i+1][j+1] += dp[i][j] % MAX
dp[i+1][j] += dp[i][j]*2*i % MAX
answer = 0
return dp[n][count] % MAX
