Lv2. 3 x n 타일링

코딩테스트 연습 > 3 x n 타일링

1. 풀이 설명

1. 홀수인 경우에는 직사각형을 채울 수 없다.

2. memo 리스트를 0으로 초기화하고,
   n이 2인 경우에는 3, n이 4인 경우에는 11로 초기화한다.

3. 2중 for문을 돌면서 memo[i] 를 업데이트 한다.

• 6부터 n까지 for문을 돌면서 memo[i] = memo[i-2] * 3 + 2
  - i-2 길이를 채우고, 남은 길이2를 채울 수 있는 방법 3가지
  - 특별한 케이스: +2
  

• i-4부터 2까지 j가 2씩 작아지면서memo[i] += 2 * memo[j]
  - 각 길이까지 채우고(memo[j]), 남은 길이를 특별한 케이스로 채울 수 있는 방법이

• 예를 들어 n = 8이라면,

  • 6칸 채우고, 남은 2칸을 채우는 방법 3가지 memo[8] = memo[6] * 3
  • 8 특별한 케이스: +2
  • 4 칸 채우고, 남은 4칸의 특별한 케이스 * memo[4] :memo[8] += 2 * memo[4]
  • 2칸 채우고, 남은 6칸의 특별한 케이스 * memo[2] :memo[8] += 2 * memo[2]

2. 나의 풀이

python

def solution(n):
    if n % 2 != 0:
        return 0
    memo = [0] * (n+1)
    memo[2] = 3
    memo[4] = 11
    for i in range(6, n+1, 2):
        memo[i] = memo[i-2] * 3 + 2
        for j in range(i-4, 0, -2):
            memo[i] += 2 * memo[j]
        memo[i] = memo[i] % 1000000007
    return memo[n]

3. 배운점

• 규칙을 찾기 어려웠던 문제다.

• 참고 문제