[BOJ][C++] 백준 2193번 이친수
Updated:
2193번 이친수
1. 문제 정보
백준 온라인 저지 [2193번 이친수] 문제의 링크입니다.
문제
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
- 이친수는 0으로 시작하지 않는다.
- 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다.
출력
첫째 줄에 N자리 이친수의 개수를 출력한다.
예제 입력1
3
예제 출력1
2
시간 / 메모리 제한
2초 / 128MB
2. 생각
- n자리 이친수의 개수를 구하는 문제는 앞서 풀어보았던 문제 10844번 쉬운 계단수 문제와 정말 비슷했습니다. 쉬운 계단수 문제는 n자리 계단수의 개수를 구하는 것입니다.
-
n-1자리의 이친수가 있을 때, n자리 이친수는
n-1자리 이친수의 오른쪽 끝자리가 0이라면 n자리에는 0과 1을 붙일 수 있고
n-1자리 이친수의 오른쪽 끝자리가 1이라면 n자리에는 0만 붙일 수 있습니다. - dp를 2차원 배열로 오른쪽 끝자리가 0과 1의 경우의 이친수의 개수를 통해 풀어나가겠습니다.
- dp[i]를 길이가 i인 이친수의 개수로 정의하고,
- dp[i][0]을 길이가 i이고, 가장 오른쪽의 숫자가 0인 이친수의 개수로 정의하고
- dp[i][1]을 길이가 i이고, 가장 오른쪽의 숫자가 1인 이친수의 개수로 정의하겠습니다.
- i가 1일 때는 이친수는 0으로 시작되지 않기 때문에 1하나로 개수는 1개입니다.
i가 2일 때부터는
i-1의 가장 오른쪽의 숫자가 1이면 0만 붙이고(개수는 그대로),
i-1의 가장 오른쪽의 숫자가 0이면 0과 1을 붙입니다.(개수는 플러스)n 이친수 개수 1 1 1 2 10 1 3 100 101 2 4 1000 1001 1010 3 5 100000 10001 10010 10100 10101 5 - 위와 같이 표로 정리해보니 n=1일때 1, n=2일 때 1, … 수의 형태가 피보나치 수열과 같음을 알 수 있습니다.
따라서 피보나치 점화식인 fibo[i] = fibo[i-1] + fibo[i-2]를 통해 문제가 풀릴 수 있습니다.
3. 소스코드 (C++)
