프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12900#

[나의 풀이1]

⌛ 5분 (모든 케이스 시간초과)

from collections import deque

def solution(n):
    answer = 0
    queue = deque([n])
    
    while queue:
        
        v = queue.popleft()
        
        if v==0:
            answer += 1
            
        if v-2>=0:
            queue.append(v-2)
        if v-1>=0:
            queue.append(v-1)
      
    return answer%1000000007

세로 2, 가로 n 넓이의 면적이 주어질 때, 2x1 크기의 타일로 모든 면적을 채울 수 있는 가짓수를 구하는 문제입니다.

문제에서 제시한 조건 중 채워야하는 세로의 길이가 2로 고정인 것이 포인트였습니다.

타일을 가로로 배치한다면 반드시 가로 2개가 위아래로 배치된 형태이고, 세로로 배치하면다면 단순히 1개만 배치하는 형태이기때문에 문제에서 풀어내고자 하는 것은 '순서를 고려한 1 혹은 2 뎃셈 연산을 통해 주어진 n을 만족시키는 경우의 수'였습니다.

이를 구현하기 위해, Queue, BFS를 활용하여 n을 만족할때까지 1 or 2 덧셈연산하여 답을 도출하였으나 시간복잡도면에서는 모두 실패하였습니다.

[나의 풀이2]

⌛ 29분

def solution(n):
    
    if n==1:
        return 1
    elif n==2:
        return 2
    else:

        dp = [0]*(n+1)
        dp[1], dp[2] = 1, 2

        for i in range(3,n+1):
            dp[i] = (dp[i-2] + dp[i-1])%1000000007
        
        return dp[n]

DP를 활용하여 시간복잡도를 개선할 수 있었습니다.

입력될 수 있는 가로의 길이 1<=n<=60000 범위 내에서

n=1, answer=1
n=2, answer=2
n=3, answer=3
n=4, answer=5
n=5, answer=8
n=6, answer=13
.
.
.

와 같이 피보나치 수열 형태로 진행되기 때문에 가로 길이 n일 때의 경우의 수 갯수는

dp[n] = dp[n-2]+dp[n-1]

입니다.

또한 '경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.'라는 조건을 해결하기 위해

dp[n] = (dp[n-2]+dp[n-1])%1000000007 

위와 같이 표현하여 조금 더 작은 수 단위로 덧셈 연산하게끔 구현하였습니다.

[다른 사람의 풀이]

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

'나의 풀이'와 같이 DP, 피보나치 수열을 활용하여 구현한 풀이입니다.

감사합니다.