코딩테스트 연습/Baekjoon
[Baekjoon] 2193번: 이친수 / dynamic
수기
2022. 4. 1. 02:18
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
피보나치 배열이다. 1자리수일때 1개, 2자리수일때 1개, 3자리수 2개, 4자리수 3개...
부분문자열 11을 배제하면 끝자리가 1일때는 1개 추가, 끝자리가 0일때는 2개 추가 할 수 있으므로 피보나치로 배열이 만들어진다. int로는 자리수가 넘어가므로 long long배열에 저장했다.
코드
//2193
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
cin.tie(NULL);
ios::sync_with_stdio(0);
int n;
long long num[91] = {0};
num[1] = num[2] = 1;
cin >> n;
for(int i=3;i<=90;i++){
num[i] = num[i-1]+num[i-2];
}
cout << num[n];
return 0;
}