반응형
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
소스코드
풀이
★ 전형적인 DP문제였습니다 ! 풀이부터 말하자면 n이 가질 수 있는 이친수의 개수는 n-1의 이친수 개수 + n-2의 이친수 개수입니다.
ex)
★ n이 6일 경우 이친수의 수는 8입니다. n으로 만들 수 있는 이친수의 개수를 dp에 저장한 뒤 이를 가지고 점화식을 세워보면, dp[n] = dp[n-1] + dp[n-2]로 세울 수 있고 이는 다음과 같이 적용됩니다 !
n = 3, 1 + 1 = 2
n = 4, 2 + 1 = 3
n = 5, 3 + 2 = 5
n = 6, 5 + 3 = 8
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 13699번: 점화식 (Python) (1) | 2023.08.17 |
|---|---|
| [백준 알고리즘] 11052번: 카드 구매하기 (Python) (6) | 2023.08.17 |
| [백준 알고리즘] 25556번: 포스택 (Python) (4) | 2023.08.16 |
| [백준 알고리즘] 27497번: 알파벳 블록 (Python) (0) | 2023.08.16 |
| [백준 알고리즘] 3111번: 검열 (Python) (1) | 2023.08.14 |