[Programmers]Python_멀리 뛰기

문제

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이상, 2000 이하인 정수입니다.

코드

from collections import defaultdict
stack = defaultdict(int) #계산한 값들은 저장해놓는다
def solution(n):
    if n <= 2: #1칸 또는 2칸일때 각각 1가지, 2가지 경우가 있다
        return n
    if stack[n]: #이미 계산한 값이면 그 값을 가져온다
        return stack[n]
    stack[n] = (solution(n - 1) + solution(n - 2)) % 1234567 #계산할때마다 1234567의 나머지를 구한다
    return stack[n]

진행 과정

예제 #1

n = 4

 

해당 문제는 전형적인 피보나치 수열 문제로 크게 어려운 점은 없다.

 

n = 1일 때 (1칸)
n = 2일 때 (1칸 * 2, 2칸)
n = 3일 때 (1칸 * 3, 1칸 + 2칸, 2칸 + 1칸)

n = 4일 떄 (1칸 * 4, 1칸 * 2 + 2칸, 2칸 + 1칸 * 2, 2칸 * 2, 1칸 + 2칸 + 1칸)

 

"1가지 -> 2가지 -> (1 + 2)가지 -> (2 + 3)가지"로 진행이 된다.

 

코드의 진행은 다음과 같다.

 

1) (solution(3) + solution(2)) % 1234567 #3과 2를 각각 재귀 호출

 

2) (solution(2) + solution(1)) % 1234567 #3일 때 2, 1을 각각 재귀 호출

3) return 2

4) stack[2] = 2

5) return 1

6) stack[1] = 1

7) (2 + 1) % 1234567 #1, 2는 2보다 작거나 같은 값이므로 그대로 return하여 나머지 값을 구한다

8) stack[3] = 3

 

9) return 2 #2일 때 2보다 작거나 같은 값이므로 그대로 return한다 

 

10) (solution(3) + solution(2)) % 1234567 = (3 + 2) % 1234567

11) return 5

 

여기서 나머지 연산 (a + b) mod m=((a mod m)+(b mod m)) mod m이 성립되기 때문에 (solution(n - 1) + solution(n - 2)) % 1234567이 가능하다.