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 ....
따라서 보텀업 방식으로 해결하면 쉽게 해결할 수 있다.
'BOJ > Python' 카테고리의 다른 글
| 백준 5585번 거스름돈 파이썬 (0) | 2022.12.03 |
|---|---|
| 백준 1541번 잃어버린 괄호 파이썬 (0) | 2022.12.02 |
| 백준 9461번 파도반 수열 파이썬 (0) | 2022.09.19 |
| 백준 1932번 정수 삼각형 파이썬 (0) | 2022.09.18 |
| 백준 1138번 한 줄로 서기 파이썬 (0) | 2022.06.28 |