[programmers] Level4. 3xN 타일링

풀이

• 홀수 입력 -> 0

• 이전 값을 저장 -> 덮어쓰는 방법 적용.

• 규칙 찾기가 어려웠는데, 경우의 수를 잘 나누어야 함. f(8)을 예로 들면,

  • 가로 길이가 8일 때, 1, 2, 2, 2, 1로 배치하는 경우가 2가지(위, 아래)

  • 가로 길이가 6 + 새로운 길이 2 붙인다면 -> f(6) x 3

  • 가로 길이가 4 + 가로 길이 4-> f(4) x 2 (1, 2, 1인 경우)

  • 가로 길이가 2 + 가로 길이 6 -> f(2) x 2 (1, ,2, 2, 1인 경우)

  • 가로 길이가 홀수일때는 생각하지 않아도 됨. 짝수인 경우만 생각하기

def solution(n):
    answer = 1
    special = 0
    for i in range(2, n+1, 2):
        answer2 = 3 * answer + special * 2
        special += answer
        answer = answer2
    return answer % 1000000007