(Python/LV2) 멀리 뛰기

728x90

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이:

def solution(n):
    res = 0
    if n <=2:
        res = n
    else:
        res = solution(n-1) + n-2
    return res % 1234567
print(solution(3))

재귀로는 풀리지 않아 dp로 작성해보려 한다.

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

windy7271