[프로그래머스] 멀리 뛰기 (lv1, Python)

 

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

프로그래머스

 

 

문제 해결 아이디어

1. 1,2로 이루어진 조합의 합계가, 주어진 수 n을 만족하는 경우의 수를 찾음. (제 경우 일일히 확인해보았습니다.)

2. 피보나치 수열의 특성을 보임을 확인함.

n	cnt	이전 값과의 차
1	1	1
2	2	1
3	3	1
4	5	2
5	8	3 (1+2)
6	13	5 (2+3)

3. 1 <= n <= 2000 범위에서 피보나치 수열을 시간제한 내에 구현할 수 있는 방법은? 동적계획법(다이나믹 프로그래밍)

4. 동적계획법 말은 거창하지만, 결국 계산된 결과를 배열 내에 저장한 후 호출하는 방식임.

5. 문제 조건에 맞게 구현해보자

 

소스코드 (Python)

def solution(n):
    '''
    규칙성을 찾는 문제
    n | cnt
    1    1
    2    2
    3    3
    4    5
    5    8
    6   13
    피보나치 수열의 특성을 보임 (1+2=3, 2+3=5, 3+5=8, 5+8=13, ...)
    '''
    if n <= 2:
        answer = n
    else:
        numbers = [1,2]   #         
        for i in range(3,n+1):
            n_cnts = numbers[i-2] + numbers[i-3]
            numbers.append(n_cnts)
        answer = numbers[n-1]
    return answer % 1234567

 

결과

굿굿