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

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

프로그래머스

 

 

문제설명

 

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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하면 됩니다.

 

문제 해결 방법

 

n이 1일때, 2일때, 3일때, 4일때의 결과를 문제에서 찾고, 5일때 결과를 만들어서 보니 피보나치 수열의 형태를 띄었다. 

피보나치 수열을 구현하여 해당문제를 해결했다. 

 

 

코드 구현

 

import itertools

def solution(n):
    answer = 0
    tmp=[0, 1, 1]
    cnt = 3
    summ = 0
    while 1:
        if n == 1:
            answer = 1
            return answer % 1234567
        elif n == 2:
            answer = 2
            return answer % 1234567
        else:
            summ = (tmp[cnt-1] + tmp[cnt-2]) 
            tmp.append(summ)
            cnt+=1
        
        if cnt == n+2:
            return summ % 1234567
    
    return answer

 

 

시간/공간 복잡도

 

최악의 경우 O(N)

 

 

최적화 및 개선 / 어려웠던 점

 

입출력의 경우를 쭉 나열해서 문제를 풀어볼 생각을 못하고, 직접 문제 그대로 구현해보려 했다. 

문제 그대로 구현하니 테스트케이스 2번부터 끝까지 시간초과가 났다. 

아무리 생각해봐도 이중 반복문을 사용하지 않고 문제를 해결할 방법이 생각나지 않아서, 힌트를 봤다. 

 

문제가 안풀리면 입출력문을 문제에서 제시한 부분을 나열해보고 그다음 부분은 직접 경우의 수를 구해 붙인뒤에 

점화식을 세워 문제를 풀 생각을 해봐야겠다. 

 

문제에 거의 점화식이 주어지는 경우도 있으니, 이런 부분 감안해서 문제를 읽어볼 것.