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

문제 설명

https://www.acmicpc.net/problem/2193

2193번: 이친수

 

 

 

해결 방향 1.

DP문제이다.

#include<iostream>
using namespace std;

int main() {

	int N;
	cin >> N;

	long long arr[91][2];

	arr[1][1] = 1;
	arr[1][0] = 0;

	for (int i = 2; i <= N; i++)
	{
		arr[i][1] = arr[i - 1][0];
		arr[i][0] = arr[i - 1][0] + arr[i - 1][1];
	}

	cout << arr[N][0] + arr[N][1];
}

arr[i][j] i자리에 j (0 or 1)가 올 경우 이친수 개수

 

long long arr[91][2];
N의 범위가 1~90이다.

그리고 N번째 마지막 자리에 올 수 있는 수는 0혹은 1 두개밖에 없으므로 arr[91][2]

 

 

arr[1][1] = 1;
arr[1][0] = 0;

첫번째 자리에 1이 왔다. 이친수 개수는 1

첫번째 자리에 0이 올 수 없으므로 이친수 개수는 0

for (int i = 2; i <= N; i++)
{
    arr[i][1] = arr[i - 1][0];
    arr[i][0] = arr[i - 1][0] + arr[i - 1][1];
}

2번째 자리부터 경우의 수이다.

 

마지막 자리(i)에 1이 온다면 그 앞자리(i-1)는 무조건 0이다.

그러므로 arr[i-1][0]이 이친수 개수가 된다.     arr[i][1] = arr[i - 1][0];

 

마지막 자리(i)에 0이 온다면 그 앞자리(i-1)는 0이 오거나 1이 올 수 있다.

그러므로 두 경우의 수를 둘 다 더한다.      arr[i][0] = arr[i - 1][0] + arr[i - 1][1];

 

cout << arr[N][0] + arr[N][1];

결과 출력

 

 

 

 

 

해결 방향 2.

위의 방식으로 문제를 해결하고 보니

이 공식이 피보나치 수열인것을 깨달았다.

코드가 훨씬 더 간결해졌다.

#include<iostream>
using namespace std;

int main() {

	int N;
	cin >> N;

	long long arr[91];

	arr[1] = 1;
	arr[2] = 1;

	for (int i = 3; i <= N; i++)
	{	arr[i] = arr[i - 1] + arr[i - 2];	}

	cout << arr[N];
}

 

arr[i]  i자리일때 이친수 개수이다.

 

long long arr[91];  N의 범위가 1~90이므로

 

 

arr[1] =1; 한자리 일 때 0은 첫번째 자리에 올 수 없어서 1만 가능하므로 arr[1]=1

arr[2] =1; 두자리 일 때 01 만 가능하므로 arr[2]=1

 

 

for (int i = 3; i <= N; i++)
{ arr[i] = arr[i - 1] + arr[i - 2]; }

3이상인 경우에는 피보나치 수열 공식 적용

 

 

cout << arr[N];

결과 출력