문제
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
알고리즘
- 자릿수에 따른 이친수를 확인해보면 쉽게 규칙을 찾을 수 있다.
- 규칙을 통해 점화식을 도출해내고 문제를 수행한다.
코드
import sys
n = int(sys.stdin.readline())
dp = [0] * 91
dp[1] = 1 # 자릿수가 1일 때, 이친수의 개수 : 1
dp[2] = 1 # 자릿수가 2일 때, 이친수의 개수 : 1
# 피보나치 수 문제를 수행하듯 점화식을 구해 문제를 수행한다.
# 점화식 : (n > 2), f(n) = f(n - 2) + f(n - 1)
for i in range(2, n + 1):
dp[i] = dp[i - 2] + dp[i - 1]
print(dp[n])github
GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법
내가 푼 코딩 테스트 문제와 해결법. Contribute to junjange/CodingTest development by creating an account on GitHub.
github.com
'CodingTest > Baekjoon' 카테고리의 다른 글
| [baekjoon] 백준 9461번(파이썬): 파도반 수열 (0) | 2021.11.30 |
|---|---|
| [baekjoon] 백준 11727번(파이썬): 2×n 타일링 2 (0) | 2021.11.29 |
| [baekjoon] 백준 1149번(파이썬): RGB 거리 (0) | 2021.11.27 |
| [baekjoon] 백준 2156번(파이썬): 포도주 시식 (0) | 2021.11.26 |
| [baekjoon] 백준 1912번(파이썬): 연속합 (0) | 2021.11.25 |