프로그래머스 level2 - 3 x n 타일링

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

n	return
4	11

 

문제 풀이

n = 1 일 때 경우의 수는 0가지 

n = 2 일 때 경우의 수는 3가지 

n = 3 일 때 경우의 수는 0가지

n = 4 일 때 경우의 수는 11가지

 

이 문제는 2 x n 타일링 문제와는 다르게 피보나치 수열로 해결할 수 없다. 그 이유는 2 x n 타일링 문제처럼 단순히 이전 두 상태로 현재 상태를 결정할 수 없고, n이 커질수록 더 복잡한 패턴과 경우의 수가 등장하기 때문에 더 많은 이전 상태를 참조해야한다.

 

점화식 설계

• 상태 정의
  • dp[n]: 3 x n 바닥을 완전히 채우는 경우의 수
• 기본 규칙
  • dp[0] = 1: 아무 타일도 없는 경우를 1가지 경우로 정의
  • dp[1] = 0: 1 x 3은 채울 수 없음
  • dp[2] = 3: 2 x 3은 타일 3개로만 채울 수 있음
• 점화식
  • dp[n] = dp[n-2] * 3 + dp[n-4] * 2 + dp[n-6] * 2 + ...
  • dp[n-2] * 3: 마지막 2칸에 특정 3가지 모양을 배치
  • dp[n-4],dp[n-6]: 4칸, 6칸전에 추가적으로 등장하는 특별한 경우의 수

따라서 dp[n] = dp[n-2] * 3 + dp[n-4] * 2 + dp[n-6] * 2 + ... 해당 점화식을 코드로 구현하면 아래와 같다.

 

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

 

시간복잡도

• 바깥쪽 반복문: i는 4부터 n까지 2씩 증가하므로 총 n // 2 - 1번 실행되므로 O(n)
• 안쪽 반복문문: j는 i-4부터 0까지 2씩 감소하므로, i / 2 -2번 실행 됨
• 총 실행 횟수:

• 이 식은 O(n2)에 비례한다. 따라서 전체 시간 복잡도는 O(n2)

공간복잡도

• 길이가 n + 1인 배열 선언
• 전체 공간복잡도는 O(n)

실행 결과

 

 

출처: https://school.programmers.co.kr/learn/courses/30/lessons/12902