[programmers] 멀리 뛰기

프로그래머스 Lv.2 멀리 뛰기

오늘도 분노의 포스팅이다..
쉽게 생각하고 풀고 운동 나가려다가 발목 잡혔다.

문제 해석
문제 해석은 어렵지 않다.

멀리뛰기에 사용 될 칸의 수 n에 대하여,
1칸 혹은 2칸씩만 뛸 수 있는 사람이 n칸을 뛸 수 있는 방법의 갯수를 구하는 문제다.
겉보기에는 순열 문제이다. (같은 것이 있는 순열)

내 첫 풀이 => 런타임 에러, 일부 오답

import math
def solution(n):
    answer = 1
    one = 0 
    for i in range(1, math.floor(n/2) + 1): 
        one = n - i*2
        answer += math.factorial(i + one) / (math.factorial(one)*math.factorial(i))
    return answer % 1234567

난 여기서 풀릴 줄 알았다.
기본적으로 1+1+1+....+1 은 항상 가능하기 때문에 answer은 1부터 시작하고,
사용할 1의 갯수를 변수 one으로 선언하였다.
i는 사용할 2의 갯수로, 1개부터 math.floor(n/2)개까지 사용 가능하다.

그래서 사용할 2의 갯수마다 [1의 갯수, 2의 갯수]를 알고 있으니,

$n! / a!b!$

이 공식을 이용해서 풀 수 있을 것이라 생각했다.
코드 실행 했을때까지는 기분이 좋았다.

하지만....

오답은 그럴 수 있다. 반례를 찾아서 풀면 되니까.
그런데 런타임 에러....? 방법 자체가 잘못 되었다는 뜻이다...
다른 방법을 찾기로 하였다.

내가 알아야 하는 알고리즘이 뭐지?

Dynamic Algorism (동적 계획법)

헬스장 문 닫을것 같아서 헬스장 갔다 와서 마저 푼다..

운동 다녀왔다. 다시 재개한다.

문제 해결을 위해 시도해본 것
내가 원래 만든 위 코드를 for문을 통해 i=1부터 i=10까지 출력 해봤다.
그랬더니.... 놀랍게도 피보나치 수열이 등장했다!!

문제에서는 n을 1이상의 정수로 정의했지만, 함수는 0일때도 동작한다.
0! = 1로 정의되어 있기 때문에, f(0) = 1로 정의된다!
그 이후의 출력값은 놀랍게도 
f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5 , f(5) = 8, ...
f(n) = f(n-2) + f(n-1)을 만족하는 피보나치 수열이었다.

왜 그럴까?

n칸을 가는 방법의 수는 = f(n)
n-1칸을 간 후에 1칸을 가는 방법(1가지) = f(n-1)
n-2칸을 간 후에 2칸을 가는 방법의 합과 같은데,
n-2칸을 간 후에 1칸+1칸을 가는 방법은 이미 f(n-1)에 포함되어 있고,
n-2칸을 간 후에 2칸을 한번에 가는 방법(1가지) = f(n-2) 이므로

f(n) = f(n-1) + f(n-2) 가 성립한다!!!

문제 해결을 위한 코드
사실 이미 피보나치 수열의 n번째 항을 구하라는 문제로 변경되었다.
그리고 그 문제는 최근에 풀었다..

def solution(n):
    # 일단 결론적으로 이 문제는 피보나치 수열 문제이다.
    # 효율성 통과가 불가능한 "같은 것이 있는 순열" 형태로 짠 함수를 1부터 10까지 돌려서 알아냈다.
    # 왜 수학적으로 동치인지는 고민해볼 문제이다.
    fib = [1,1,2] # 피보나치 수열의 index 0,1,2에 해당하는 값을 미리 넣어준다.
    if n < 3:
        return fib[n]
    else:
        for i in range(3,n+1):
            fib.append(fib[i-1]+fib[i-2])

    return fib[-1] % 1234567

당연하게도 이 코드의 효율성은.. 매우 좋을 것이다. ㅋㅋ

이렇게 문제를 해결하는 데 성공했다.

꿀잠을 잘 수 있게 되었다.