【코딩】 C 언어로 "이상한 나라의 셈법"

C 언어로 "이상한 나라의 셈법"

 

추천글 : 【C 언어】 C 언어 목차

---

Q. 어떤 나라에서는 이진법을 사용한다. 그런데 그 나라의 사람들은 0이 연속적으로 붙는 수를 싫어한다. 숫자를 셀 때도 0이 연속적으로 붙는 수를 싫어한다. 그래서 다른 나라와 무역을 할 때 어려움이 따른다. 이 나라의 왕은 이 문제를 해결하기 위해 자기 나라 숫자를 십진법으로 바꾸는 프로그램을 만들려고 한다. 왕을 도와 프로그램을 작성하여라. (ref)^]

 

입력

이 왕국에서 사용하는 수 n을 입력한다. (이때 입력되는 것은 이진법이고, 0이 연속적으로 붙는 수는 없다.) (1 ≤ n ≤ 2²¹) 

참고 : 1 → 1, 10 → 2, 11 → 3, 101 → 4, 110 → 5, 111 → 6, 1010 → 7

 

출력

n을 십진법으로 출력한다.

 

#include <stdio.h>
#include <stdlib.h>

int Converting(char *array, int *Fibo, int array_size){
	if(array_size <= 3){
		if(array_size == 1) return 1;
		if(array_size == 2) return 2 + array[1];
		return 2*array[1] + array[2] + 3;
	}
    
	if(array[1] == 0){ // 101…
		char array_2[array_size - 2];
		int i;
		for(i=2; i<array_size; i++){
			array_2[i-2] = array[i];
		}
		return Fibo[array_size-1] + 1 + Converting(array_2, Fibo, array_size - 2);
		/* Fibo[array_size] - 1 + Converting(array_2, Fibo, array_size - 2) - (Fibo(array_size - 2) - 1) */
	}
	else if(array[2] == 0){ // 110…
		char array_2[array_size - 3];
		int i;
		for(i=3; i<array_size; i++){
			array_2[i-3] = array[i];
		}
		return Fibo[array_size] + 1 + Converting(array_2, Fibo, array_size - 3);
		/* Fibo[array_size] - 1 + Fibo[array_size - 1] - Fibo[array_size - 2] +
			Converting(array_2, Fibo, array_size - 3) - (Fibo(array_size - 3) - 1) */
	}
	else{ // 111…
		char array_2[array_size - 2];
		int i;
		for(i=2; i<array_size; i++){
			array_2[i-2] = array[i];
		}
		return Fibo[array_size] + 1 + Converting(array_2, Fibo, array_size - 2);
		/* Fibo[array_size] - 1 + Fibo[array_size - 1] - Fibo[array_size - 2] + Fibo[array_size - 2] -
			Fibo[array_size - 3] + Converting(array_2, Fibo, array_size - 2) - (Fibo(array_size - 2) - 1) */
	}
}

int main(int argc, char *argv[]) {
	char array[23];
	int Fibo[23];
	int i; char ch;
	Fibo[1] = 1;
	Fibo[2] = 2;
	for(i = 3; i <= 22; i++){ // Fibo[i] equals 1010…(2) (size: i) (귀납적으로 증명)
		Fibo[i] = Fibo[i-1] + Fibo[i-2] + 1;
	}
	i = 0;
	while(1){
		ch = getchar();
		if(ch < 30) break;
		array[i] = ch - '0';
		i ++;
	}
	printf("%d", Converting(array, Fibo, i));
	return 0;
}

 

입력 : 2016.02.16 11:31