Level 3 멀리 뛰기 Python 3

https://programmers.co.kr/learn/courses/30/lessons/12914?language=python3 

코딩테스트 연습 - 멀리 뛰기

 

최종 풀이

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_멀리뛰기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

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

---

풀이 과정

 규칙을 찾기 위해 N이 1~6일 경우 경우의 수를 구해보았다.

N	경우의 수	answer
1	1	1
2	11, 2	2
3	111, 12, 21	3
4	1111, 112, 121, 211, 22	5
5	11111, 1112, 1121, 1211, 2111, 122, 212, 221	8
6	111111,11112,11121, 11211, 12111, 21111, 1122, 1212, 1221, 2112, 2121, 2211, 222	13

dp[i] = dp[i-2] + dp[i-1]인 피보나치 수열이다.

def solution(n):
    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = (dp[i-2] + dp[i-1])%1234567
    return dp[n]
#시간복잡도 = O(n), 공간복잡도 = O(n)