[프로그래머스] Lv2 - 멀리 뛰기

김멉덥·2023년 8월 30일

programmers python

알고리즘 공부

목록 보기

94/171

문제

프로그래머스 연습문제

Lv 2. 멀리 뛰기 (Python)
https://school.programmers.co.kr/learn/courses/30/lessons/12914

코드 구현

def solution(n):
    if (n <= 3):
        return n

    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2

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

    return dp[n]

풀이

풀이 및 해설

어떤 규칙이 있는지 찾는 과정에서 많이 헤맸다 … 알고보니 피보나치 수열 !!
1칸 2칸 3칸 4칸 5칸
(1) (1,1) (2) (1,1,1) (1,2) (2,1) (1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2) (1,1,1,1,1) (1,1,1,2) (1,1,2,1) (1,2,1,1,) (2,1,1,1) (1,2,2) (2,1,2) (2,2,1)
1개 2개 3개 5개 7개
따라서 n칸을 뛰는 경우는
- n-2 칸을 뛴 후에 + 2칸을 더 뛴다.
- n-1 칸을 뛴 후에 + 1칸을 더 뛴다
- n칸을 뛰는 방법 = (n-2칸을 뛰는 방법) + (n-1칸을 뛰는 방법)
3칸 까지는 n과 같은 수를 리턴하므로 if문 조건을 추가해준 뒤, 4칸부터 for문으로 계산
- 2칸을 뛴 후 + 2칸을 더 뛴다. → (1,1) or (2) + (1,1,) or (2)
- 3칸을 뛴 후 + 1칸을 더 뛴다. → (1,1,1) or (1,2) or (2,1) + (1)
피보나치인걸 눈치채지 못해서 예상밖으로 너무 시간을 오래 썼던 문제라 나중에 한번 다시 풀어보기

1칸	2칸	3칸	4칸	5칸
(1)	(1,1) (2)	(1,1,1) (1,2) (2,1)	(1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2)	(1,1,1,1,1) (1,1,1,2) (1,1,2,1) (1,2,1,1,) (2,1,1,1) (1,2,2) (2,1,2) (2,2,1)
1개	2개	3개	5개	7개