공부 기록장
[백준 - Python] 2193. 이친수 (DP) 본문
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
코드
N = int(input())
dp = [0] * (N+1)
for i in range(1, N+1):
if i == 1 or i == 2:
dp[i] = 1
else:
dp[i] = dp[i-1] + dp[i-2]
print(dp[N])
N이 1일때부터 쭉 적어가면서 이친수의 개수를 직접 세어보았고,
그 개수들 사이의 규칙을 찾아 점화식을 세웠다.
무작정 규칙을 찾으려고 하기보다는
이전 이친수들을 활용해서 이번 이친수들이 어떻게 나올까에 초점을 두고
점화식을 생각해보려고 했는데,
해당 점화식에 대한 그림이 잘 표현된 것이 있어 가져와봤다.
참고 자료
https://cijbest.tistory.com/17
'코딩 테스트 > 백준 문제 풀이' 카테고리의 다른 글
| [백준 - Python] 1149. RGB거리 (DP) (0) | 2024.02.15 |
|---|---|
| [백준 - Python] 11053. 가장 긴 증가하는 부분 수열 (DP) (0) | 2024.02.15 |
| [백준 - Python] 9461. 파도반 수열 (DP) (0) | 2024.02.15 |
| [백준 - Python] 11726. 2xn 타일링 (DP) (0) | 2024.02.10 |
| [백준 - Python] 1003. 피보나치 함수 (DP) (0) | 2024.02.10 |