[프로그래머스] 멀리 뛰기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

1. 각 수마다 경우의 수를 저장할 딕셔너리를 생성한다. d = {}
2. 처음에 움직이지 않는 경우와 1칸 움직이는 경우를 딕셔너리에 추가한다. d[0] = 1  d[1] = 1
3. 다음 숫자인 2부터 입력받은 수까지 반복하며 다음 수의 경우의 수를 저장한다. 다음 수의 경우의 수는 이전 수의 경우의 수와 그 이전 수의 경우의 수를 더한 값이다. for i in range(a, n + 1): d[i] = d[i - 1] + d[i - 2]
4. 1칸과 2칸을 이동하여 각 칸으로 갈 수 있는 방법은 전의 결과에서 1칸을 가던지 그 이전의 결과에서 2칸을 가는 방법뿐이기 때문이다. n칸 = (n - 1)칸 + 1칸 or (n - 2)칸 + 2칸
5. 결과는 딕셔너리에서 해당 수의 값이다. answer = d[n]
6. 결과를 1234567로 나눈 나머지를 반환한다. return answer % 1234567

반응형

3. 소스코드

def solution(n):
    answer = 0
    
    d = {}
    d[0] = 1
    d[1] = 1
    for i in range(2, n + 1):
        d[i] = d[i - 1] + d[i - 2]
    
    answer = d[n]

    return answer % 1234567