티스토리 뷰
접근방식을 두가지로 해보았다.
1) 규칙을 파악해서 피보나치 수열로 판단하는방법
1과 0이 나오는 개수는 기본적으로 피보나치 수열이다.
0이 나오는 개수 1, 0, 1, 1, 2 , 3, 5,...
1이 나오는 개수 0, 1, 1, 2, 3, 5
규칙을 파악해보면,
0이나오는개수, 1이나오는 개수 모두 피보나치수열이며
특히 0이나오는개수의 수열을보면
0번째항을 제외하고는 모두 1이 나오는 개수와 한칸씩 밀리는 관계임을 확인할 수 있다.
0이 나오는 개수 1, 0, 1, 1, 2 , 3, 5,...
1이 나오는 개수 0, 1, 1, 2, 3, 5...
이를 이용하여 피보나치 함수를 구해주는 함수를 작성하고, 그 값을 산출해내면 되는것
결국 0과 1의 개수를 물어봤지만, 피보나치 수열을 계산하라는것과 같은 셈이다.
2) 간단하게 카운팅 해주는 방법
간단하게 푸는 또다른방법은,
주어진 피보나치 수열에 관한 함수를 활용, 0과 1을 카운트해주는 식으로 풀 수 있다.
1번과 다른점은, 피보나치 수열을 계산하여 그 결과 값을 가져가는 접근법과, 단순히 계산 과정속에서 카운팅을 해주는 접근의 차이..?
int fibonacci(int n) { if (n==0) { printf("0"); return 0; } else if (n==1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }} |
이함수를 이용, 0일때 0에 해당하는 변수에 count ++
1일때 1에 해당하는 변수에 count++를 해줘서 그 값을 후에 출력하는 방식이다.
[코드예시]
1. 일반적 풀이 방법. (재귀) + 간단하게 카운팅.
주어진 피보나치 수열을 활용.
1) 2차원 배열로
if (inputData == 0) {
result[i][0] += 1;
return 0;
}
if(inputData ==1) {
result[i][1] += 1;
return 1;
}
return 피보나치 재귀;
2) 혹은, 전역변수로 카운팅
if (inputData == 0) {
count0++; (전역변수)
return 0;
}
if(inputData ==1) {
count1++; (전역변수)
return 1;
}
return 피보나치 재귀;
등으로 해주신후에, 카운팅한 숫자 출력.
2. 일반적 풀이 방법. (재귀) + 피보나치 수열로 판단 계산
1번과 다를건 없다. 피보나치 수열을 계산하는 함수를 만들어서 그 리턴값을 출력.
0과 1일때
int fib(int n){
if(n<=1)
return n;
else
return fib(n-1)+fib(n-2);
}
int main() 함수 :
if (fib < 2){
fib0 = (fib) ? 0 : 1;
}
*메인함수에서 예외사항에 대한 처리해준다.
3. 피보나치 수열로 판단 계산 + 메모제이션(DP)
int main(){
int fib;
int fib0,fib1 = 0;
int testcase;
scanf ("%d", &testcase);
for (int t = 1 ; t <= testcase ; t++) {
scanf("%d", &fib);
if (fib < 2){
fib0 = (fib) ? 0 : 1;
}else{
fib0 = fibDP(fib-1);
}
fib1 = fibDP(fib);
printf("%d %d\n", fib0, fib1);
}
return 0;
}
int fibDP(int n){
int arr[100],i;
arr[0] = 0, arr[1] = 1;
for(i=2 ; i<n+1 ; i++)
arr[i] = arr[i-1]+arr[i-2];
return arr[n];
}
DP/메모제이션을 활용한 방법입니다.
* 참고 : http://blog.naver.com/j_js1215/220793005951
이방식은, Time Complexity를 줄여줍니다.
4. 피보나치 수열로 판단 계산 + 점화식 활용.
int main(){
int fib;
int fib0,fib1 = 0;
int testcase;
scanf ("%d", &testcase);
for (int t = 1 ; t <= testcase ; t++) {
scanf("%d", &fib);
if (fib < 2){
fib0 = (fib) ? 0 : 1;
}else{
fib0 = fib_calc(fib-1);
}
fib1 = fib_calc(fib);
printf("%d %d\n", fib0, fib1);
}
return 0;
}
int fib_calc(int n){
double result;
result = (pow(((1+sqrt(5))/2),n) - pow(((1-sqrt(5))/2),n)) / sqrt(5) ;
return (int)result;
}