[level 2] 멀리 뛰기

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

 

---

 

 

n에 따라 나올 수 있는 경우의 수를 생각해보면 다음과 같다. 

n	경우의 수
1	1
2	2
3	3
4	5
5	8

 

확인해보면 1과 2 이후부터는 F(n) = F(n-1) + F(n-2)로 점화식 형태를 띄고 있음을 알 수 있다. 

이를 활용하여 알고리즘을 고민해보았다. 

 

 

문제 풀이 접근법1

1) 0부터 n까지 0으로 채운 리스트 distance를 선언한다.

2) distance[0]에는 0, distance[1]에는 1, distance[2]에는 2가 들어가게 한다.

3) for문으로 3번 부터는 distance[i]의 값에 (i-1) + (i-2)의 값이 들어가게 한다.

4) distance[n]에 1234567을 나눈 나머지 값을 return한다. 

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

 

1에서 런타임 에러가 났다.

찾아보니까 메모리 할당...어쩌구 때문에 그렇다고

그래서 다른 방법으로 시도해보았다. 

 

 

문제 풀이 접근법2

1) a와 b를 각각 1, 2로 초기화한다.

2) n이 1, 2, 3일 때는 각각 1, 2, 3, 을 answer에 넣는다.

3) 4이상부터는 for문을 돌며 a와 b의 값을 차례대로 업데이트 한다. 이후 a+b의 값을 answer에 넣는다.

4) answer에 1234567을 나눈 나머지 값을 return한다. 

def solution(n):
    answer = 0
    a, b = 1, 2
    
    if n == 1:
        answer = 1
    elif n == 2:
        answer = 2
    elif n == 3:
        answer = a+b
    else:
        for i in range(3, n):
            a, b = b, b+1
        answer = a+b
        
    return answer % 1234567

 

..ㅎ 테스트 케이스 1번과 2번을 제외하고 모두 실패했다. 

 

 

문제 풀이 접근법3

1) 0이 하나 들어가 있는 리스트 answer를 정의한다.

2) 1부터 n+1까지 반복문을 돌린다.

3) 이때, i가 1이거나 2이이면 각가 1과 2를 answer에 추가한다.

4) 3부터는 answer[i-1]+answer[i-2] 값을 answer에 추가한다. 

4) answer[n] % 1234567을 나눈 값을 반환한다. 

def solution(n):
    answer = [0]
    
    for i in range(1, n+1):
        if i == 1:
            answer.append(1)
        elif i == 2:
            answer.append(2)
        else:
            answer.append(answer[i-1] + answer[i-2])
        
    return answer[n] % 1234567

 

 

---

사실 처음에는 점화식인 줄도 몰랐다.

출처: 나무위키(피보나치 수열)

 

나무위키에서 설명해준 예시를 잘 기억하고 있으면 좋을 듯하다.

"계단을 오르는 수" 와 같은 문제들은 점화식을 사용하여 푼다<< 를 알았으니 다음 번에는 꼭!

 

 

---

 

다른 분들 문제풀이

def jumpCase(num):
    a, b = 1, 2
    for i in range(2,num):
        a, b = b, a+b
    return b

#아래는 테스트로 출력해 보기 위한 코드입니다.
print(jumpCase(4))

그냥 2부터 시작하면 되는 거였어..!!!!

반성합니다. 앞으로 더 고민해보겠습니다.