📖 연습문제 > 멀리 뛰기
📖What I thought
- 처음엔 타겟 넘버와 동일한 유형의 문제인 줄 알고 bfs로 풀었음 근데 시간 초과 엔딩…
- 잘 생각해보니까 결과값을 더 작은 값의 결과에서 구할 수 있는 전형적인 dp문제였다 dp문제를 너무 오랜만에 풀어서 기억이 안 났음 ;;
📖풀이
📎Dynamic Programming
def solution(n):
dp = [0 for _ in range(n+2)]
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n] % 1234567📖What I learned
- n항을 구하기 위해 n-1항 이하의 결과가 반복적으로 사용될 때 dp를 까먹지 말자!!!
dp 문제 구별 방법
- 문제를 같은 형태의 문제로 나눌 수 있음?
- 하위 문제의 계산이 반복됨?
- 최적화 or 최대/최소화 or 특정 잡업의 경우의 수를 구하는 유형의 문제임? → 1, 2만으로 헷갈리면 3번 참고