김로그

2193번 이친수

2193번 이친수

이친수를 구하는 문제이다. 문제의 조건을 다음과 같다.

  1. 이친수는 0으로 시작하지 않는다.
  2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
  3. N(1≤N≤90)

조건 1에서 이친수의 처음시작은 1임을 알 수 있다. 조건에 따라서 나올 수 있는 이친수들을 N에 따라 써보면

1: 1
2: 10
3: 101 100
4: 1010 1001 1000
5: 10101 10100 10010 10000 10001

이된다. 몇번 더 써보면 피보나치수열이 됨을 알 수 있다.


reference