[백준2193] 이친수 (C++)

1. 문제

백준 2193

 

2. 설명

3. 접근

1->1 (1개)

2->10 (1개)

3->100, 101 (2개)

4-> 1000, 1001, 1010 (3개)

5-> 10000, 10001, 100010, 10100, 10101 (5개)

 

피보나치수열의 규칙을 찾을 수 있습니다. 시간과 메모리양을 줄이기 위해서 탑다운이 아닌 bottom-up 방식으로 풀었습니다. 점화식은 다음과 같습니다.

num[i] = num[i - 1] + num[i - 2]

 

처음에 num배열을 int로 설정해서 오류가 났습니다. 입력값이 47을 넘으면 결과가 int범위를 넘어서서 overflow가 발생하기 때문입니다. long long으로 변경해서 해결하였고 앞으로 제출하기전에 항상 범위도 점검해야겠습니다.

 

4. 코드

#include <iostream>
using namespace std;

long long i_chin_soo(int number_of_digit, long long* num);

int main() {
	int number_of_digit;
	long long num[91] = { 0 };

	cin >> number_of_digit;
	cout << i_chin_soo(number_of_digit, num);
}

long long i_chin_soo(int number_of_digit, long long* num) {
	int i = 0;
	num[1] = 1;
	num[2] = 1;

	for (i = 3; i < number_of_digit+1; i++) {
		num[i] = num[i - 1] + num[i - 2];
	}
	return num[i-1];
}