[C++] 백준 2193번 이친수

1. 문제이해

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

2193번: 이친수

 

0과 1로만 이루어져있으면서, 아래 조건을 만족하는 수를 이친수라고 한다.

N이 주어질 때, N자리 이친수의 개수를 구하는 것이 목표이다.

 

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 연속으로 2번 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

 

 

 

2. 문제풀이

 

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

처음 문제를 봤을 때 든 생각은, 1과 0 을 적절히 다 조합해봐야하나.. 라는 생각이었다.

이전 조합한 숫자가 1이면 0, 0이면 1또는 0을 적절히 조합해 하나씩 넣어보자고 생각했다.

그러나 한번 쭉 숫자들을 나열해보니, 그럴필요가 없던 간단한 문제였다.😅

아래 그림을 보자.

 

 

위 그림은 N = 1 ~ 7 까지 구할 수 있는 모든 이친수의 경우이다.

각각의 경우의 이친수의 개수를 살펴보면,

(N = 3 부터) N번째 이친수의 개수 = (N - 1)번째 이친수의 개수 + (N - 2)번째 이친수의 개수 임을 알 수 있다.

이를 통해 구현한 소스코드는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

int main() {
	int N;
	// int 이용시 오류발생
	long long pinary_num[91];
	
	cin >> N;

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

	cout << pinary_num[N];

	return 0;
}

N자리 이친수의 개수를 구하는 코드이다.

여기서, N자리 이친수의 개수를 pinary_num[N]이라는 배열에 저장한다.

단, 주의해야 할 점은 int 형 이용시 오류가 발생하므로, 반드시 long long 형을 이용해주어야 한다는 점이다.

(int형을 사용하게 되면, N값이 큰 경우 이친수의 개수가 int형의 범위를 넘어서게 된다.)

 

N가지 이친수의 개수를 저장하는 pinary_num[N] 함수에 각각 0, 1, 2 일 때의 값을 저장해 놓은 다음,

(0일때에는 없으므로 0으로 대입, 1부터는 2. 문제풀이에서의 그림과 동일)

2. 문제풀이에서 구한 점화식을 이용해 N자리 이친수의 개수를 구해주었다.

 

 

---

한번 안써봤으면 꽤나 힘든 방법으로 풀지 않았을까, 하는 생각이 드는 문제이다.

뭐든 일단 노트에 풀이법을 여러가지 적어놓고 시작하는 편인데,

안되는 때도 많지만, 가끔 이런 문제가 나오면 뿌듯하다.🥰

 

문제에 대한 질문이나 지적은 언제나 감사하게 받고있습니다.😊