3xn 타일링 Pgs#12902

3xN 타일링 PGs#12902

Python 코드 보기

def solution(n):
    answer = 0
    if n%2 == 1:	# n이 홀수면 타일 채우기 불가능.
        return 0
    target = n//2	# 몇 번 DP를 실행할 지 결정
    
    tiling = [0] * (target+1)
    tiling[1] = 3	# 규칙을 따르는 값
    extra = 2		# 규칙 외 값

    for i in range(2,target+1):
        tiling[i] = tiling[i-1]*3 + extra
        extra += tiling[i-1]*2
    
    answer = tiling[target]%1000000007
    return answer

☝ 입력 형식

• 가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다.

• 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다.

• 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다
  • 타일을 가로로 배치 하는 경우
  • 타일을 세로로 배치 하는 경우
• 직사각형의 가로의 길이 n이 매개변수로 주어진다. (n <= 5000의 자연수)

🤞 출력 형식

• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

🤟 구현 과정

1. 알고리즘 결정

코드를 구현하기 앞서, 일일히 타일을 깔아보는 방식으로 해야 하는지, 점화식으로 규칙성을 유도할 수 있을지를 결정해야한다.

5000x3의 타일에 일일히 타일을 까는 방식은 시간 복잡도가 끔찍할 것이다. 그렇다면 규칙성을 찾아보는 것이 낫겠다.

2. 규칙성 찾기

• n=2 : 3가지 경우의 수
• n=4 : 11가지 경우의 수 = 3*3 + 2가지 경우의 수
• n=6 : 39가지 경우의 수 = 11*3 + 8_{= 2+(3*2)}가지 경우의 수
  • 4x3 타일을 까는 방법 = 2x3타일을 까는 방법*2x3타일을 까는 방법 + extra
  • extra를 결정하는 점화식을 찾았는지 검사.

3. 점화식 설정

• extra = i-1번째까지 경우의 수의 합
• i+1번째 = i번째*3 + extra

4. 코딩

복잡하지 않은 점화식이므로, 간단히 구현할 수 있다.

🍀 Pain Points

1. 점화식 증명

• 만약 프로그래머스의 채점 기능을 통해서 내 점화식이 맞는지 확인할 수 없다면 어떻게 할 것인가?
• n=8일때만 되어도 100가지가 넘는데, 직접 그릴 건가에 대한 해결방안이 필요하다.