[백준] 2193번 이친수

문제: 2193번: 이친수

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
//#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n; // n 자리 이친수

	// first: 0으로 끝나는 수, second: 1로 끝나는 수
	vector<pair<long long, long long>> nums(n + 1);
	nums[1] = { 0, 1 }; // 1
	if (n>=2)
		nums[2] = { 1, 0 }; // 10
	for (int i = 3; i < n + 1; i++) {
		long long zeroCnt = nums[i - 1].first + nums[i - 1].second;
		long long oneCnt = nums[i - 1].first;

		nums[i] = {zeroCnt, oneCnt};
	}
	cout << nums[n].first + nums[n].second;

	return 0;
}

 

0으로 끝나는 수와 1로 끝나는 수의 개수를 각각 저장해놓은 다음 이 값을 이용하도록 했다.

 

0으로 끝나는 수는 자기신 다음으로 0과 1 둘 다 올 수 있고, 1로 끝나는 수는 자기 다음으로 0만 올 수 있다.

 

즉, 0으로 끝나는 수의 개수는 이전 요소의 수 전체와 같고 1의 개수는 이전 요소의 0으로 끝나는 수의 개수와 같다.