문제

문제 링크

코드

bfs

from collections import deque


answer = 0


def bfs(n):
    global answer
    q = deque()
    q.append(1)
    q.append(2)
    
    while q:
        now = q.popleft()
        if now == n:
            answer = (answer % 1000000007) + 1
        elif now > n:
            continue
        else:
            q.append(now + 1)
            q.append(now + 2)
          
 def solution(n):
 	bfs(n)
 	return answer

DP

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

접근 방식

처음에 bfs로 문제를 풀었더니 시간 초과가 났다.
너무나 간단한 논리의 문제였기에 논리의 문제가 아닌 최적화의 문제임을 깨달았다.
그래서 최적화 기법 중에 하나인 DP를 적용하기 위해 점화식 관계가 있는지 살펴보았다.
그러니 f(n) = f(n-1) + f(n-2) 라는 피보나치 수열의 점화식이 문제에 존재함을 찾았다.
따라서 이를 코드로 구현하여 문제를 해결할 수 있을 줄 알았으나..
문제의 조건 중에 1000000007으로 값을 나눠서 반환하라는 조건이 있었다.
그렇기에 이 조건을 반영하기 위해 위의 코드처럼 점화식을 변경해주었다.
여기서 키포인트는 반환할 때 마지막에만 나머지 연산을 하면 안되는 이유를 아는 것이다.
마지막에만 나머지 연산을 하게 되는 경우, 파이썬의 원시 타입의 범위를 n까지 가는 중간에 초과해서 값이 변질 될 수 있다. 따라서 애초에 점화식 관계에서 나머지 연산을 처리해야만 한다.