멀리 뛰기

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12914

❔ 문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때,

(1칸, 1칸, 1칸, 1칸) 
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸) 
(2칸, 2칸) 

멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요.

⚠️ 제한사항

• n은 1 이상, 2000 이하인 정수입니다.

---

💡 풀이 (사용언어 : Python)

문제대로 풀었지만 에러가 떠서 다른 사람들의 질문 내용을 보니 N-1,N-2에 각각 1234567의 나머지를 더한값을 N으로 해서 수열로 풀어야 답으로 인정되는 문제였다.

처음에 파이썬으로 풀어본 코드는 ‘같은 것이 있는 수열’ 개념을 이용해 공식을 추정해 Factorial을 이용해 문제를 풀었다. 초기 테스트 케이스와 정답 테스트 케이스 6번까지는 정답이었지만 이후엔 모두 오답과 오버플로우 처리가 되었다. integer division result too large for a float 라는 에러는 나누는 분모에 너무 큰수가 나오면 뜨는 에러라고 한다. (신기하게 /부분을 //로 대체해주면 에러가 안떴다.)
하지만 이 개념을 이용한 풀이는 정답으로 인정 받는 것이 불가능했고
피보나치 수열 공식을 이용한 모범답안 풀이를 공부하고 작성했다.

• 처음 푼 파이썬 코드 (경우의 수 합 + 팩토리얼 공식)

import math

def solution(n):
    
    answer = 0
      
    if n % 2 == 0:
        k = n // 2
        length = k
        
        while(k >= 0):
            ans = math.factorial(length) // (math.factorial(k) * math.factorial(length - k))
            answer += ans
            k -= 1
            length += 1
            
    else:
        k = n // 2
        length = k + 1
        
        while(k >= 0):
            ans = math.factorial(length) // (math.factorial(k) * math.factorial(length - k))
            answer += ans
            k -= 1
            length += 1
       
    return int(answer) % 1234567

• DP를 이용한 피보나치 수열 공식 풀이

def solution(n):
    
    fibo = [0] * (n + 1)
    fibo[1], fibo[2] = 1, 2
    
    for i in range(3, n + 1):
        fibo[i] = (fibo[i-1] + fibo[i-2]) % 1234567
    
    return fibo[n]