반응형
https://school.programmers.co.kr/learn/courses/30/lessons/12945
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제풀이
아래와 같이 DP를 적용할 수 도 있지만 널널한 테스트 케이스 특성상 굳이 구현할 필요없이 반복문만 돌려도된다. 피보나치 수열은 n이 커질때 값이 기하급수적으로 늘어나기 때문에 가능하면 재귀나 반복문에서 1234567로 나머지 계산을 해주는게 훨씬 빠르다.
Top Down (2024-02-05 lru_cache를 이용한 방법으로 수정)
from functools import lru_cache
import sys
sys.setrecursionlimit(10000000)
@lru_cache(maxsize=None)
def solution(n):
if n == 0:
return 0
elif n == 1:
return 1
return (solution(n - 1) + solution(n - 2)) % 1234567
Bottom Up
def solution(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567
return dp[n]
