문제

https://school.programmers.co.kr/learn/courses/30/lessons/12902#qna

풀이

아이디어

• 도저히 규칙이 보이지 않아서 다음 풀이를 참고했다.
  https://s2choco.tistory.com/24
• 내가 궁금했던 것은 각 단계 별로 <특이한 모양>이 계속 늘어날 거라고 생각했는데 의외로 항상 2개씩이었다.

코드

def solution(n):
    DP = [0, 3, 11]
    index = int(n/2)
    
    if index < 3:
        return DP[index]
    
    for i in range(3, index+1):
        temp = (3*DP[i-1] + sum(DP[1:i-1])*2 + 2) % 1000000007
        DP.append(temp)
    
    return DP[index]