📌 구해야 하는 정답

0과 1로만 이루어진 수들 중, 아래 두 조건을 만족하는 수를 이친수라고 합니다.

1. 이친수는 0으로 시작하지 않습니다.
2. 이친수에서는 1이 두번 연속 나타나지 않습니다.

N이 주어졌을 때 N자리 이친수의 개수를 구하는 문제입니다.

📌 풀이 하기

1️⃣ 풀이 방법 고민하기

N자리 이친수는 어떻게 구할 수 있을까요?

완전 탐색

완전탐색을 한다면, N자리 이진수는 총 2^N개 존재하며, 이를 모두 탐색해야 합니다.

N은 최대 90으로, 이렇게 탐색하면 시간안에 모든 탐색이 불가능 합니다.

N을 만드는 규칙 탐색하기

다른 방법으로 문제를 풀기 위해 우선 이친수를 만드는 규칙을 더 자세히 살펴봅시다.

작은 값부터 탐색해보겠습니다.

n = 1

• 1

n = 2

• 10