[python3] 멀리 뛰기 lv.2

시도 1) nCm 으로 해결해보려,, 했는데

def nCm(n,m) :
    if m == 0 : return 1
    else :
        r = 1
        for i in range(n-m+1,n+1) :
            r*=i
        t = 1
        for i in range(1,m+1) :
            t*=i
        return r//t

def solution(n):
    one = n
    two = 0
    summ = 0
    while one >= 0 :
        summ += nCm(one+two, min(one,two))
        one-=2
        two+=1
    return summ%1234567 # 나머지를 구하는 문제. 문제 잘읽자

 

 

 

풀이) (점화식) 피보나치

1 -> (1) : 1

2 -> (1,1), (2) : 2

3 -> (1,1,1), (1,2), (2,1) : 3

4 -> (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2) : 5

5 -> (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) : 8

결론 : 전전꺼 맨 뒤에 2를 붙이거나, 전꺼 맨 뒤에 1을 붙이거나 둘 중 한가지로 표현할 수 있다.

def solution(n):
    a=0
    b=1
    for i in range(n) :
        a,b = b,a+b
    return b%1234567