[프로그래머스] 쌍둥이 빌딩 숲

https://school.programmers.co.kr/learn/courses/30/lessons/140105?language=python3# 

프로그래머스

해설

나머지 연산이 있는걸 보니 전형적인 dp 문제이다. (n,c) 를 (n-1,c-1) 과 (n-1,c)로 나누어 생각한다.

 

 

새로들어온 n이 두개가 다 가장 뒤로 배치된다고 하자. n은 어차피 가장 크므로 나머지 경우의수는 solution(n-1, c-1)이 될 것이다.

 

만약 n의 건물 사이에 아래처럼 다른건물이 들어오거나 앞서있다면?

(n, n-1)의 이 한쌍의 조합을 그냥 하나의 건물이라 생각할 수 있을 것 이다! 그럼 나머지 경우의 수는 2 * solution(n-1,c) 이다.

그런데 여기서 잠깐, 단순 n,n-1만 짝지을 수 있을 까. (1,2), (2,3), (3,4)... (n-1,n) 각각 쌍을 하나의 건물이라 생각하고 작업을 수행하면 2*(n-1)*solution(n-1,c) 가 된다

 

즉 점화식은 다음과 같다

 

solution(n,c) = solution(n-1,c-1) + 2*(n-1)*solution(n-1,c) 

 

 

import math
import sys
sys.setrecursionlimit(10**7)

dp = [ [-1] * 101 for _ in range(101)]

for i in range(1,101):
    dp[i][i] = 1
    dp[i][0] = 0

def solution(n, c):
    if dp[n][c] != -1:
        return dp[n][c]
    dp[n][c] = (solution(n-1,c-1) + solution(n-1,c)*2*(n-1)) %1000000007

    return dp[n][c]