Programmers / 3 x n 타일링 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 3 x n 타일링 (2단계) -  DP

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12902

프로그래머스

문제 설명

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

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

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

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

제한사항

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

입출력 예

n	result
4	11

입출력 예 설명

입출력 예 #1
다음과 같이 11가지 방법이 있다.

 

 

 

 

 

 

 

 

 

 

---

나의 풀이

 

n은 짝수만 와야 타일링을 할 수 있다.

n이 커질 수록 각각 기존의 타일을 이어서 만들 수도 있고, 새로운 타일을 만들 수 있다.

 

새로운 타일의 모양을 한번 보자.

각각 새로운 타일 2개씩 (위아래 반전으로) 이 만들어 질 수 있다.

 

그리고 기존의 타일과 새로운 타일을 붙여서도 타일을 만들 수 있다.

f(2) = 3

 

f(n) = f(n-2)*3 + f(n-4)*2 + ... + f(2)*2 + 2

라는 점화식을 얻을 수 있다.

여기서 x = n의 짝수 라고하자,

f(n) = f(n-1)*3 + f(n-2)*2 + ... + f(2)*2 + 2

점화식을 조금 더 보기 편하게 만들 수 있다.

 

첫번째 풀이(테스트 통과, 채점 오답)

def solution(n):
    answer = 0
    x = n // 2
    d = [0] * (x+1)
    if n % 2 == 1:
        return 0 # 홀수인 경우는 타일을 만들 수 없다.
    
    if x == 1:
        return 3
    if x == 2:
        return 11
    if x == 3:
        return 41
    
    for i in range(3,x+1):
        d[i] = (d[i-1] * 3 + sum(d[1:i-1]) * 2 + 2) % 1000000007
        
    return d[x]

 

두번째 풀이 (런타임 에러)

def solution(n):
    answer = 0
    d = [0] * (n+1)
    if n % 2 == 1:
        return 0 # 홀수인 경우는 타일을 만들 수 없다.
    if n == 0:
        return 0
    if n == 2:
        return 3
    if n == 4:
        return 11
    
    
    for i in range(6,n+1,2):
        d[i] = (d[i-2] * 3 + sum(d[0:i-2:2]) * 2 + 2) % 1000000007
        
    return d[x]

 

모범 답안

메모리를 고려해서 처음부터 메모리를 확장 시킨게 아니라 그냥 추가하는 형식으로 계산해준다.

 

def solution(n):
    d = [0,3,11]
    x = int(n/2)
    if n % 2 != 0: return 0
    if x < 3: return d[x]

    for i in range(3, x+1):
    	# d[i:j] -> d에서 d가 i인 원소부터 j-1인 원소까지의 sub-array
        d.append((3*d[i-1]+sum(d[1:i-1])*2+2)%1000000007)

    return d[x]

 

---

※ 알아야 할 것

- https://s2choco.tistory.com/24 블로그에서 보다 더 자세한 설명을 하고있다. 풀이 참조하시길...

- dp문제는 생각보다 메모리를 고려하면서 풀어야하는 경우가 많다..