Level 3 2 x n 타일링 Python3

https://programmers.co.kr/learn/courses/30/lessons/12900?language=python3# 

코딩테스트 연습 - 2 x n 타일링

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_2xn타일링.py

hwayeon351/Programmers-Algorithms

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

---

풀이 과정

1. 첫시도 -> 오답

처음에 문제를 읽고 가로가 n인 타일을 채우기 위해 필요한 가로가 1인 타일과 가로가 2인 타일 개수의 경우의 수를 구해주고, 각 경우에서의 조합을 사용하여 모두 더하는 쪽으로 문제를 풀려고 시도했다.

즉, 다음과 같이 표현된다.

n	조합	answer
1	1	1
2	11, 2	2
3	111, 12, 21	3
4	1111, 112, 121, 211, 22	5
5	11111, 1112, 1121, 1211, 2111, 122, 212, 221	8

따라서 조합식을 활용하기 위해 팩토리얼 값을 구해나가며 정답을 구해주는 방식으로 시도하였는데 런타임에러가 났다.

import sys
sys.setrecursionlimit(100000)
def factorial(n, fac):
    if fac[n] != 0: return fac[n]
    fac[n] = n*factorial(n-1,fac)
    return fac[n]
def solution(n):
    fac = [0]*(n+1)
    fac[0] = 1
    answer = 0
    for sq2 in range(0, n//2+1):
        sq1 = n-2*sq2
        answer += (factorial(sq1+sq2, fac)/(factorial(sq1, fac)*factorial(sq2, fac)))
    return answer%1000000007
#시간복잡도 = O(n), 공간복잡도 = O(n)

입력의 제한 사항에서 n이 60000이하의 값을 주어진다고 하였는데 그렇다고 하면 최대 60000!을 구해야한다. 팩토리얼 값을 구할 때 dp방식을 도입해서 구하였지만, 팩토리얼 값이 너무 큰 숫자가 만들어질 수 있기 때문에 런타임에러가 난다.

 

2. 다른 풀이 1

 팩토리얼을 구해서 푸는 방법이 아닌 다른 규칙을 찾아보면, 위의 표를 보면 answer[i] = answer[i-1] + answer[i-2]이라는 규칙을 찾을 수 있다. 익숙한 dp 알고리즘의 형태라는 것을 알 수 있었고, bottom-up방식으로 구현하였다. 하지만 이번에는 answer값에 대해 메모이제이션을 하는 것이다.

def solution(n):
    dp = [0]*(n+1)
    dp[0] = 0
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = (dp[i-1]+dp[i-2])%1000000007
    return dp[n]
#시간복잡도 = O(n), 공간복잡도 = O(n)

여기에서 조심해야 할 부분은 dp값을 저장할 때마다 1000000007을 나눈 나머지 값을 넣어줘야 한다. 큰 n 값이 들어오면 너무 값이 커지기 때문이라는 것을 염두해야한다.

 

3. 다른 풀이 2

 위의 풀이를 더 간단하게 표현해봤다. 이전 값과 그 이전 값을 더해나가며 마지막 최종 값만 뽑아내면 되기 때문에 항상 전의 2값만 갱신해주면 된다. 두 변수만 필요하므로 위 코드보다 더 나은 공간복잡도를 보인다.

def solution(n):
    a, b = 1, 1
    for i in range(n):
        a, b = b, a+b
    return a%1000000007
#시간복잡도 = O(n), 공간복잡도 = O(1)