[프로그래머스] 멀리 뛰기 (.python 파이썬)

---

 

문제의 핵심 

효진이는 한 번에 1칸 또는 2칸을 뛸 수 있다. 

칸이 n개 있을 때 , 효진이가 끝에 도달하는 방법의 수를 구하는 것이다. 

 

접근 방법

효진이가 끝에 도달하는 방법은 피보나치 수열과 유사하다. 

 

- (n-1) 번째 칸에서 1칸을 뛰어 n번째 칸에 도달

- (n-2) 번째 칸에서 2칸을 뛰어 n번째 칸에 도달 

 

따라서 ways(n) = ways(n-1) + ways(n-2) 이 된다.

---

코드 

def solution(n):
    temp = dict()
    
    temp[0] = 1
    temp[1] = 1
        
    for i in range(2, n+1):
        temp[i] = temp[i-1] + temp[i-2]
    
    answer = temp[n] % 1234567    
    return answer

 

 

풀이 

주어진 문제에서 'n'의 범위가 1부터 2000까지이기 때문에 , 모든 범위에 대해 효율적으로 답을 계산할 수 있는 방법이 필요하다. 

만약 n=4와 같은 작은 값에 대해서만 답을 구한다고 하면 더 간단한 방법으로도 계산 가능하다. 

 

def count_ways(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    return count_ways(n-1) + count_ways(n-2)

# 테스트 예제
print(count_ways(4))  # 출력: 5

 

하지만, 재귀함수는 'n'이 커질 수록 계산 시간이 급격히 늘어나기 때문에 효율적이지 않다. 

 

따라서, 효율적인 동적 프로그래밍(DP) 방식을 사용하는 것이 중요하다. 

이를 통해 중복 계산을 피하고, 계산 시간을 크게 줄일 수 있다.