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

 

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

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

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

프로그래머스

 

문제 설명

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

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

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

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

제한사항

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

---

 

입출력 예

n	result
4	5

입출력 예 설명

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

---

동적프로그래밍의 대표적인 문제이다.

점화식으로 문제를 풀어나가면 간단하게 풀린다.

 

길이가 1일때 경우의 수: 1가지

- 직사각형을 세로로 두는 경우

 

길이가 2일때 경우의 수: 2가지

- 직사각형을 가로로 두는경우

- 직사각형을 세로로 두는 경우

길이가 3일때 경우의 수: 3가지

- 제일 뒤를 세로(길이1)로 두는 경우 -  나머지 부분의 길이는 2가 남으므로 길이가 2일때 경우의 수 2가지

- 제일 뒤를 가로(길이 2)로 두는 경우 -  나머지 부분의 길이는 1가 남으므로 길이가 1일때 경우의 수 1가지

 

..

점화식

d[i] = d[i-1] + d[i-2]

 

 

나의 풀이 (첫번째 풀이, 효율성 테스트 실패)

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

효율성이 통과 안되는 이유: 메모리 공간을 많이 써서

해결 방법 - 점화식에서 1000000007으로  나누면 해결됨 

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

 

다른 풀이

def solution(n):
    a, b = 1, 1
    for i in range(1, n):
        a, b = b, (a + b) % 1000000007
    return b

---