[종만북] 타일링(TILING2) (Python)

문제 출처:

www.algospot.com/judge/problem/read/TILING2

algospot.com :: TILING2

문제 풀이 :

• 종만북에서 보통 포기한다는 8장 DP를 공부하며 푼 문제
• DP로 풀어야하는 문제라는 걸 미리 알고 도전했기 때문에 다른 DP 문제보다 쉽게 풀 수 있었다.

 

• 우선 맨 앞에 타일을 놓는 경우는 2가지가 있다.
  • 2x1 짜리 타일 1개를 놓는 경우
  • 2x2 짜리 타일 2개를 놓는 경우

가장 왼쪽에 타일을 놓는 경우의 수

• DP를 풀때 자주 생각하는건 "뒷일은 다음사람한테 넘기자!" 라는 생각이다. 위에 그림을 보면 가장 왼쪽에 타일을 하나 두고 남은 길이는 n-1 길이, n-2 길이 만 남는다.
• 이를 새로운 n'이라고 생각하면 계속해서 왼쪽에만 타일을 놓는 경우로 생각하면된다. 
• 즉,
  DP[i] = 길이 i의 바닥에 타일을 놓는 경우의 수
  로 보고 문제를 해결했다.
• 보통 직관적으로 풀기 좋은 재귀함수를 이용해서 풀었고 이때 초기값을 잘 설정해주어야한다. 또한 답을 구할때 mod를 이용 해야하는데 python으로 푸는경우엔 자동으로 형변환을 해주기 때문에 과정중간에서 mod연산자를 쓰지 않아도 정답이 나온다. 단 C++과 같은 언어를 사용하여 풀땐 신경써주어야 한다.

dp = [-1]*101
mod = 1000000007
c = int(input())

def init_():
    global dp
    dp = [-1]*101
    dp[1]=1
    dp[2]=2
    dp[3]=3
    dp[4]=5

def solve(N):
    global dp

    if(dp[N]!=-1):
        return dp[N]%mod

    dp[N] = (solve(N-1)%mod+solve(N-2)%mod)%mod
    return dp[N]

for _ in range(c):
    init_()
    n = int(input())
    print(solve(n))