https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되
www.acmicpc.net
N=5일때 모든 경우의 수를 생각해보면,
10000
10001
10010
10100
10101
이렇게 다섯가지다. 0000은 N[0], 0001은 N[1], 0010은 N[2], 0100과 0101은 N[3]... 이런 식으로 끝에서 i번째 자리가 1일 경우 가짓수를 N[i]라고 하면, N[i]=N[i-2]+N[i-3]+...N[0]이다.
이것만 눈치채면 코딩은 매우 쉽다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
#include <stdio.h>
long long int crazy[91]={1,1,};
int main(void){
int N;
scanf("%d",&N);
for(int i=2; i<=N; i++){
for(int j=0; j<i-1; j++)
crazy[i] += crazy[j];
}
printf("%lld",crazy[N]);
}
|
'알고리즘 문제' 카테고리의 다른 글
| [C/C++ 백준 1699번] 제곱수의 합 (Silver 3) (0) | 2020.05.05 |
|---|---|
| [C/C++ 백준 1912번] 연속합 (Silver 2) (0) | 2020.05.05 |
| [C/C++ 백준 2579번] 계단 오르기 (Silver 3) (0) | 2020.05.04 |
| [C/C++ 백준 9461번] 파도반 수열 (Silver 3) (0) | 2020.05.04 |
| 1일 1개 알고리즘 문제 풀기 (0) | 2020.05.04 |
