[프로그래머스💯] 코딩테스트 연습 > 연습문제 > 멀리 뛰기 > / Python 문제풀이 (2가지방법)

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

해답1 - 재귀

import sys
sys.setrecursionlimit(10 ** 6)


def solution(n):
    cached = [-1 for _ in range(n+1)]
    cached[0] = 1
    cached[1] = 1

    def find(num):
        if cached[num] != -1:
            return cached[num]
        cached[num] = find(num-2) + find(num-1)
        return cached[num]

    return find(n) % 1234567

 

해답2 - 재귀 X

def solution(n):
    res = [0 for _ in range(n+1)]
    res[0] = 1
    res[1] = 1

    for i in range(2, n+1):
        res[i] = res[i-1] + res[i-2]
    return res[n] % 1234567

 

풀이)

두 해답 모두 기본적인 방법은 같습니다.

 

n 의 숫자를 나누는 방법 :

 

<1, (n-1)을 나누는 방법>

<2, (n-2)를 나누는 방법>

이 두가지의 합의 수입니다.

 

예)

2 -> (1,1 / 2)
3 -> 1, (1,1 / 2) +(1,1 / 2), 1

4 -> 1, (3 나누기), + 2, (2 나누기)

.

.

.

7 ->  (1 / 6을 나누는 가지 수) + (2 / 5를 나누는 가지 수)

.

.

.

n -> 1, (n-1 나누기) + 2, (n-2 나누기)

 

 

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges