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

문제 바로가기

2193번: 이친수

풀이 과정

길이가 \(i-1\)일 때, 0으로 끝나는 이친수의 수를 \(\text{number_of_zeros}_{i-1}\), 1로 끝나는 이친수의 수를 \(\text{number_of_ones}_{i-1}\)이라고 하면

$$\text{number_of_zeros}_{i} = \text{number_of_zeroes}_{i-1}+\text{number_of_ones}_{i-1}$$

$$\text{number_of_ones}_{i} = \text{number_of_zeroes}_{i-1}$$

이다. 왜냐하면 마지막이 1일 때 0은 붙을 수 있지만 1을 붙을 수 없어서 이후 단계에서 0만 하나 더 붙을 수 있지만, 마지막이 0일 때에는 1과 0 둘 다 붙을 수 있기 때문이다.

코드

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N;
	cin >> N;

	vector<long long> number_of_ones = { 1 };
	vector<long long> number_of_zeros = { 0 };
	for (int i = 1; i < N; ++i) {
		number_of_ones.push_back(number_of_zeros[i - 1]);
		number_of_zeros.push_back(number_of_zeros[i - 1] + number_of_ones[i - 1]);
	}

	cout << number_of_ones.back() + number_of_zeros.back() << EL;

	return 0;
}