쌍둥이 빌딩 숲

import sys; sys.setrecursionlimit(1000000) cache = {(1, 1): 1} def solve(i, j): if i == 0 or j == 0: return 0 if (i, j) in cache: return cache[(i, j)] v = solve(i-1, j-1) + solve(i-1, j) * 2 * (i-1) cache[(i, j)] = v % 1000000007 return cache[(i, j)] def solution(n, count): # cache[i][j] : i종류의 빌딩을 가지고 j종류의 빌딩이 구분되게 세우는 경우의 수 # # cache[i+1][j+1], 즉, i+1번째 종류의 빌딩이 보여서 j+1종류가 되려면 맨 앞에 세워야 함. # 따라서 cache[i+1][j+1] = cache[i][j] # # cache[i+1][j] : 즉, i+1번째 종류의 빌딩이 가려지게 세우려면, # 두 빌딩은 무조건 이어붙인 상태로 배치되고, 2*i 개의 큰 빌딩들 오른쪽 아무데나 들어가도 되므로 # 2*i 종류. # 따라서 cache[i+1][j] = cache[i][j] * 2*i # # 정리하면 # cache[i][j] = cache[i-1][j-1] + cache[i-1][j] * 2*(i-1) return solve(n, count)