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

 

❎ 1차 풀이

from itertools import product

def solution(n):
    num_list = [1, 2]
    count = 0

    for i in range(1, n + 1):
        for perm in product(num_list, repeat=i):
            if sum(perm) == n:
                count += 1
                continue

    return count % 1234567

모든 조합을 중복이 가능한 product를 사용하여 만들고, 그 합이 n이 되면 카운트를 증가시키는 방법으로 해보았다. 

역시나, 시간초과가 발생하였다.

 

 

이 문제 카테고리가 DP인데, 동적프로그래밍 대표유형인 피보나치와 같은 패턴을 가지고있는 문제였다.

 

n=1

(1)

n=2

(1,1)

(2)

n=3

(1,1,1)

(1,2)

(2,1)

n=4

(1,1,1,1)

(1,2,1)

(2,1,1)

(1,1,2)

(2,2)

 

✅ 정답풀이

def solution(n):
    answer=0
    dp1, dp2=1,1
    for i in range(2,n+1):
        dp1,dp2=dp1+dp2,dp1

    return dp1%1234567

n=4를 기준으로 보았을때, 이전값(n=3)에 1을 추가, 2번째 이전값(n=2)에 2를 추가하는 패턴을 가지고 있는것을 확인할 수 있다.

값을 구하는것이 아닌 카운트를 구하면되기 때문에  dp[n]=dp[n-1]+dp[n-2] 이런식으로 점화식을 구하면된다.

 

카운트만하면되므로, 배열을 사용하지 않고, 변수로 숫자만 더해주었다.