[백준/C++]#2193 - 이친수

풀이

#include <iostream>
using namespace std;

int main() {
	long long a[91],b[91];
	int n;
	cin >> n;
	a[1]=0,b[1]=1;
	for (int i=2; i<=n; i++) {
		a[i]=a[i-1]+b[i-1];
		b[i]=a[i-1];
	}
	cout << a[n]+b[n];
	return 0;
}

개념

다이나믹 프로그래밍 문제 중 하나이다.

이 문제는 int 이외의 자료형 long long을 사용해야하는 문제이다.

n이 90개까지 입력된다면 배열에 저장되는 값은 2,147,483,647보다 커지므로 long long으로 범위를 늘려야한다.

---

풀이 

이친수를 구하기 위해 문제를 2가지 case로 나누었다.

①직전 값이 0 ( 뒤에 0 또는 1 가능)

②직전 값이 1 ( 뒤에 0만 가능)

 

그리고 자신의 가장 작은 자릿수 값이 0인 경우를 a[]배열, 1인 경우를 b[]배열이라고 가정한다.

위의 식은

①a[n] = a[n-1]+b[n-1]

②b[n] = a[n-1]

로 나타낼 수 있다.

 

이제 반복문에서 a와 b 배열을 각자 계산한 다음, 합쳐서 출력하면 된다.

---

+a

위에 내가 풀은 식보다 더 깔끔한 해결법이 있다.

2가지가 있는데, 첫번째는 똑같이 2개의 공간을 사용하지만, 1차원 배열 2개가 아니라 2차원 배열 하나를 사용하는 것이다. 이 경우 D[n][1]을 사용한다.

#include <iostream>
using namespace std;

int main() {
	long long D[91][1];
	int n;
	cin >> n;
	D[1][0]=0, D[1][1]=1;
	for (int i=2; i<=n; i++) {
		D[i][0]=D[i-1][0]+D[i-1][1];
        D[i][1]=D[i-1][0];
	}
	cout << D[n][0]+D[n][1];
	return 0;
}

이 풀이는 위 풀이와 거의 똑같다.

 

두번째 풀이는 중점을 n번째에 맞춰서 경우를 나누는 것이다.

n이 0일 때, D[n-1]과 경우가 같다.

n이 1이라면, 그 앞에는 반드시 0이 와야 하므로, D[n-2]와 경우가 같다.

이 때 D[n]=D[n-1]+D[n-2]이다. 풀이는 아래와 같다.

#include <iostream>
using namespace std;

int main() {
	long long D[91];
	int n;
	cin >> n;
	D[1]=1, D[2]=1;
	for (int i=3; i<=n; i++) {
		D[i]=D[i-1]+D[i-2];
	}
	cout << D[n] << '\n';
	return 0;
}