티스토리 뷰

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)로 구할 수 있습니다.

 

 

구현 코드

 

'Coding Test > 백준' 카테고리의 다른 글

[C++/Python] 백준 2156 - 포도주 시식  (0) 2020.07.30
[C++/Python] 백준 9465 - 스티커  (0) 2020.07.29
[C++/Python] 백준 11057 - 오르막 수  (0) 2020.07.27
[C++/Python] 백준 10844 - 쉬운 계단 수  (0) 2020.07.24
[C++/Python] 백준 9095 - 1, 2, 3 더하기  (0) 2020.07.23