문제
풀이
- n에 따른 결과값은 아래 테이블과 같다.
| n | value |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
| 6 | 13 |
- n-1번째의 값과 n-2번째의 값을 더하면 현재 값이 나오는 규칙을 확인할 수 있다.
- 이를 수행하기 위해서 dp를 이용하였으며 bottom-up 방식으로 구현하였다.
- n의 범위가 크므로
1234567를 나눈 나머지를 매 dp 값을 구할 때 수행해야지 효율적이다.
코드
# https://school.programmers.co.kr/learn/courses/30/lessons/12914
# programmers, level2: 멀리 뛰기, python3
def solution(n: int) -> int:
d = [0] * 2001 # dp table 초기화
d[1], d[2] = 1, 2
for i in range(3, n+1):
d[i] = (d[i-2] + d[i-1]) % 1234567
return d[n]
if __name__ == '__main__':
print(solution(4)) # 5
print(solution(3)) # 3결과
