문제

문제 링크

BFS 풀이

from collections import deque

def bfs(n):
    answer = 0
    q = deque()
    q.append(0)
    
    while q:
        now = q.popleft()
        
        if now == n:
            answer += 1
            continue 
        if now + 1 <= n:
            q.append(now+1)
        if now + 2 <= n:
            q.append(now+2)
    
    return answer
    
 def solution(n):   
    # - bfs -
    answer = bfs(n)
    answer = answer % 1234567
    return answer

문제점

시간 초과가 발생했다.
즉, 쓸데 없는 노드가 불필요하게 많이 발생했다는 뜻이다.

경우의 수 풀이

dp_f: dict = {0:1,1:1}
def factorial(num):
    global dp_f
    if num in dp_f.keys():
        return dp_f[num]
    else:
        answer = num * factorial(num-1)
        dp_f[num] = answer
        return answer
def solution(n):    
    # - 경우의 수 -
    answer = 0
    max_two_step = n // 2
    for i in range(max_two_step+1):
        one_step = n - (i*2)
        answer += int(factorial(i + one_step) / (factorial(i) * factorial(one_step)))
    answer = answer % 1234567
    return answer

문제점

시간 초과가 났다.
팩토리얼을 이용했다는 것부터 사실 깨름칙한 접근이긴 했다.
사실 여기서 보다 더 dp스럽게 접근한다는 걸 깨달아야 했다.

DP 풀이

dp_f: dict = {0:1,1:1}
def factorial(num):
    global dp_f
    if num in dp_f.keys():
        return dp_f[num]
    else:
        answer = num * factorial(num-1)
        dp_f[num] = answer
        return answer

def solution(n):   
    # - dp -
    # 알고리즘이 맞는데도 시간 초과가 날 때는 dp를 적용해본다.
    # dp의 존재 여부를 파악하기 위해선 점화식을 세울 수 있는 지 생각해본다.
    answer = formula(n) % 1234567
    return answer

고친 점

시간 초과가 주요하게 발생할 때는 DP를 고려해보자.

DP가 강력하게 적용될 수록 시간 초과를 줄일 수 있다.

즉 시간 초과가 문제 되는 상황에서, 점화식 관계를 찾을 수 있는 문제라면 DP를 적용해본다!