Coding Test/백준
[C++/Python] 백준 2193 - 이친수
Junchoi
2020. 7. 28. 14:00
문제 링크
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
N이 1일 때는 1, 2일때 1가지의 방법이 있습니다.
N이 3이상일 때부터는
N-1에서 오른쪽에 0을 더한 방법과
N-2에서 오른쪽에 01을 더한 방법의 합이 됩니다.
따라서 DP(N) = DP(N-1) + DP(N-2)로 구할 수 있습니다.
구현 코드