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

문제

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

[나의 풀이]

⌛ 시간초과 (31/100 점)

def solution(n):
    from collections import deque

    answer = 0
    queue = deque([0])

    while queue:

        v = queue.popleft()

        if v>n:
            continue
        elif v<n:
            queue.append(v+1)
            queue.append(v+2)
        else:
            answer += 1

    return answer%1234567
    

주어진 입력값 n을 1 혹은 2만으로 더할 수 있는 케이스를 구하는 문제입니다. 이를 구현하기 위해 BFS로 n보다 작을 시에 1 혹은 2를 더한 케이스를 추가하며 모든 경우의 수를 구하였지만 다수 케이스에서 시간초과가 발생하여 다른 풀이를 참고하였습니다.🐻🐻🐻

[다른사람의 풀이1]

def solution(n):
    if n<3:
        return n
    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]%1234567

DP로 해결가능한 문제였습니다.

n=1이면 [1], n=2이면 [1,1]/[2]인 경우로 해결이 가능합니다. 이를 기반으로 n=3인 경우를 구한다면 n=1일때의 경우에서 +2만 하면 되고, 또한 n=2인 경우에 +1만 하면되기 때문에 n=1,n=2인 경우의 수를 더하면 됩니다. 그리하여 DP로 피보나치 수열을 구하듯이 입력값 n을 완성하는 케이스를 n-1,n-2 케이스의 합을 구하는 방식을 구현할 수 있습니다.🐻‍❄️🐻‍❄️🐻‍❄️

[다른사람의 풀이2]

def solution(n):
    # n=1 일 때 1 반환
    if n == 1: return 1
    else: 
        # DP 테이블 초기화
        dp = [0] * (n+1)
        dp[1] = 1
        dp[2] = 2

        # 점화식 적용, 숫자가 커지는 것을 방지하기 위해
        # 계속해서 나머지 연산자 활용하기
        for i in range(3,n+1):
            dp[i] = (dp[i-2] + dp[i-1]) % 1234567

        # DP 테이블 마지막 값 반환
        return dp[-1]

이외 다른 풀이도 동적프로그래밍으로 해결한 방법이였습니다.🐼🐼🐼

감사합니다.