문제링크
https://www.acmicpc.net/problem/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자리 이친수의 개수를 출력한다.
조건
- 시간 제한 : 2s
- 메모리 제한 : 128MB
해설
이친수의 개수가 구성되는 원리를 이해하면 쉽게 해결할 수 있다.
이친수는 첫번째 숫자가 1이여야 하고, 1이 연속으로 두 번 올 수 없다. 첫번째 1 다음에는 무조건 0이 와야하고, 그 뒤에는 1이 연속으로 두 번 오지 않는 선에서 숫자가 적절하게 배치되면 된다. 이때, 두번째 1이 어디에 있는지에 따라 아래 예시처럼 경우를 나눌 수 있다. (없음 - 뒤에서 1번째 - 뒤에서 2번째 - 뒤에서 n-2번째)
1 : 1
2 : 10
3 : 100, 101
→ 100 + 101
4 : 1000, 1001, 1010
→ 1000 + 1001 + 101_
5 : 10000, 10001, 10010, 10100, 10101
→ 10000 + 10001 + 1001_ + 101__
6 : → 100000 + 100001 + 10001_ + 1001__ + 101___해당 경우에 맞는 개수를 더해주면 쉽게 해결이 가능하다.
풀이
이친수의 구성 원리에 따라 아래와 같이 경우를 나눌 수 있다. 1번째 숫자는 무조건 1이고, 1이 연속 2번 올 수 없으므로 2번째 숫자는 무조건 0이 된다. 3번째 숫자부터 1이 올 수 있다. 1이 3번째 숫자에 온다면 4번째 숫자는 무조건 0이 되며, 5번째 숫자부터 1이 올 수 있다. 또는 1이 4번째 숫자에 5번째 숫자는 무조건 0이 들어가고 6번째 숫자부터 1이 올 수 있다. 여기에서 올 수 있다는 것은 작은 문제로 또 나뉜다는 것을 의미한다.
이 패턴을 정리해보면 1, 2번째 숫자는 10으로 고정, 3번째 숫자부터 1이 올 수 있고, 그 다음 1이 어디에 오는지에 따라 작은 문제로 나뉘어진다.
1 : 1
2 : 10
3 : 100, 101
→ 100 + 101
4 : 1000, 1001, 1010
→ 1000 + 1001 + 101_
5 : 10000, 10001, 10010, 10100, 10101
→ 10000 + 10001 + 1001_ + 101__
6 : → 100000 + 100001 + 10001_ + 1001__ + 101___- 1이 더이상 없는 경우 : 1개 ( 10000...000)
- 오른쪽에서 1번째에 1 : n=1인 이친수
- 오른쪽에서 2번째에 1 : n=2인 이친수
- 오른쪽에서 3번째에 1 : n=3인 이친수
- 오른쪽에서 k번째에 1 : n=k인 이친수
- 오른쪽에서 n-2번째에 1 : n=n-2인 이친수
n자리의 이친수의 개수는 1이 없는 경우의 수 ~ 1이 n-2자리에 있는 경우의 수의 총 합과 같다. 이를 코드로 구현하면 아래와 같다.
1이 더이상 없는 경우에 1을 추가해주어야 하므로 sum에는 미리 1을 넣어두었다. sum에는 1~n-2까지의 pinary의 합이 담겨있다. sum에 2칸 전의 pinary값을 더하고, 이 값을 pinary[i]에 대입한다.
long sum = 1;
pinary[1] = 1;
for(int i = 2; i <= n; i++) {
sum += pinary[i-2];
pinary[i] = sum;
}
참고로 이 값은 피보나치 수열의 값과 같다.
코멘트
왜 피보나치랑 같아지는거지..? ㅋㅋㅋ
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
int n;
cin >> n;
vector<long> pinary(n+1);
long sum = 1;
pinary[1] = 1;
for(int i = 2; i <= n; i++) {
sum += pinary[i-2];
pinary[i] = sum;
}
cout << pinary[n];
return 0;
}
Uploaded by Notion2Tistory v1.1.0