Programmers/프로그래머스-멀리 뛰기-python

문제

풀이

• n에 따른 결과값은 아래 테이블과 같다.

n	value
1	1
2	2
3	3
4	5
5	8
6	13

• n-1번째의 값과 n-2번째의 값을 더하면 현재 값이 나오는 규칙을 확인할 수 있다.
• 이를 수행하기 위해서 dp를 이용하였으며 bottom-up 방식으로 구현하였다.
• n의 범위가 크므로 1234567를 나눈 나머지를 매 dp 값을 구할 때 수행해야지 효율적이다.

코드

# https://school.programmers.co.kr/learn/courses/30/lessons/12914
# programmers, level2: 멀리 뛰기, python3
def solution(n: int) -> int:
    d = [0] * 2001  # dp table 초기화
    d[1], d[2] = 1, 2

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

    return d[n]

if __name__ == '__main__':
    print(solution(4))  # 5
    print(solution(3))  # 3

결과

출처 & 깃허브

programmers 멀리 뛰기
github