문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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은 1 이상, 2000 이하인 정수입니다.

풀이

2로 나누어 몫을 two라는 변수에, 나머지를 one이라는 변수에 넣고 숫자 2와 1의 개수의 조합을 구해주는 방식으로 풀었다.

ex) n=5
1,2,2 -> 1 한 개와 2 두 개를 가지고 조합구하기
1,1,1,2 -> 1 세 개와 2 한 개를 가지고 조합구하기
1,1,1,1,1

하지만,
7번부터 시간초과 뜬다.

from itertools import combinations


def solution(n):
    answer = 0
    two = n//2
    one = n % 2
    if n == 1:
        return 1
    while 1:
        answer += len(list(combinations(range(two+one), two)))
        if two != 0:
            two -= 1
            one += 2
        else:
            break

    return answer % 1234567

n을 1부터 봤을때
1 - 1
2 - 2
3 - 3
4 - 5
5 - 8
6 - 13
규칙을 찾을 수 있었다.
바로 앞에 두 개를 더하면 현재의 가지수가 된다.

따라서,
dp를 통해 이를 해결할 수 있었다.

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