ps:problems:boj:2193
이친수
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 2193 |
문제명 | 이친수 |
레벨 | 실버 3 |
분류 |
피보나치 |
시간복잡도 | O(nlogn) |
인풋사이즈 | n<=90 |
사용한 언어 | Python |
제출기록 | 29200KB / 72ms |
최고기록 | 52ms |
해결날짜 | 2021/12/23 |
풀이
- 간단한 DP 문제이다.
- f[i]를 0으로 끝나는 길이 i짜리 이친수, g[i]를 1로 끝나는 길이 i짜리 이친수라고 하면 점화식은 아래처럼 나온다
- f[i+1] = f[i]+g[i], g[i+1] = f[i]
- g[i]를 f[i-1]로 치환하면 f[i+1] = f[i] + f[i-1]이니까 피보나치 수열 형태가 된다. 우리가 구하는 N자리 이친수는 f[N]+g[N]이니까 f[N+1]과 같다.
- n번째 피보나치 수를 구하는 것은 O(logn)에 가능하다
코드
"""Solution code for "BOJ 2193. 이친수".
- Problem link: https://www.acmicpc.net/problem/2193
- Solution link: http://www.teferi.net/ps/problems/boj/2193
Tags: [Fibonacci]
"""
from teflib import combinatorics
def main():
N = int(input())
print(combinatorics.fibonacci(N))
if __name__ == '__main__':
main()
- Dependency: teflib.combinatorics.fibonacci
ps/problems/boj/2193.txt · 마지막으로 수정됨: 2021/12/23 12:13 저자 teferi
토론