[프로그래머스] 멀리뛰기

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

 

내 풀이

나는 처음에 BFS를 생각했다. 그래서 queue를 사용해서 문제를 풀면 된다고 생각했다.

from collections import deque
def solution(n):
    queue = deque()
    count = 0
    queue.append(n)
    while(queue):
        num = queue.popleft()
        if(num == 0):
            count += 1
            continue
        if(num >= 2):
            queue.append(n-1)
            queue.append(n-2)
        else:
            queue.append(n-1)
    return count % 1234567

코드 상으로는 겁나게 깔끔하다. 그러나 문제 결과는 실패. 이유는 시간 초과였다. 에효효

일단 0이나 1일 경우를 제외하고 계속 2의제곱으로 숫자가 늘어난다. 작은 수면 상관없겠지만 최대가 2000인 상황에서는... 어효효 시간 초과가 일어나는게 당연했다. 

 

모범 답안

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

다른 답안도 많고 짧은 답안도 많았지만 이 답안이 이해가 쉬웠다.

일단 d라는 배열은 1부터 사용한다. 그래서 n+1개의 배열을 사용했고, 각 배열은  i번째 걸었었을 때 나올 수 있는 경우의 수를 가지고 있다.

그래서 i = 1일때는 1밖에 없으므로 1

2일때는 1씩 2번 가는 방법과 2 한번 가는 방법, 총 2가지가 있다

 

만약에 3을 갈 때는 만약에 1+1+1, 2+1, 1+2 => 총 세 가지가 있는데

이는 1까지 가는데 걸리는 경우의 수(i-2, 1에서 2칸을 가면 3) + 2까지 가는데 걸리는 경우의 수(i-1, 2에서 1칸을 가면 3)를 구하면 알 수 있다.

그래서 마지막 n번째 인덱스에 있는 값이 n번째로 이동했을 때 나오는 경우의 수다.

 

*궁금했던점*

i-2번째에서 i번째로 이동하는 경우의 수는 2가지 아닌가?라는 생각을 했었다.i-2에서 2칸 이동하는 경우의 수와 1칸 두 번 이동하는 경우의 수 두 개가 있지 않나..?근데 i-2에서 1칸 두 번 이동하는 경우에는 i+1번째를 들리게 된다.이는 i+1번째의 경우의 수이기 때문에 i-2도 2칸 이동하는 경우의 수 하나만 적용하면 된다!

 

그래서 n[i] = n[i-2] + n[i-1]을 적용해야한다. 

 

참.. 코테를 위해선 수학적 능력도 많이 중요하다는 걸 느낀다.