BOJ/Python
백준 2193번 이친수 파이썬
띵지니어
2022. 9. 20. 07:32
반응형
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
내 답안
import sys
input = sys.stdin.readline
dp = [0] * 91
dp[0] = dp[1] = 1
N = int(input())
if N < 3:
print(dp[N-1])
else:
for i in range(N-2):
dp[i+2] = dp[i+1] + dp[i]
print(dp[N-1])REVIEW
6자릿수까지 노가다 했는데,
결론은 규칙이 있는 피보나치수열이었다.
1, 1, 2, 3, 5 ....
따라서 보텀업 방식으로 해결하면 쉽게 해결할 수 있다.
반응형