이친수 (feat. 백준, 2193번)

이친수
https://www.acmicpc.net/problem/2193

2193번: 이친수

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2193
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register long long N, dp[91][2];
	dp[1][0] = dp[1][1] = 1;
	cin >> N;
	for (register int i = 2; i <= N; ++i)
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1], dp[i][1] = dp[i - 1][0];
	cout << dp[N][1] << endl;
	return 0;
}
// *&)*@*

1. N을 1이라고 했을때, 0이 올수도 있고 1이 올수도 있지만 1만 출력합니다. (ans = 1)
2. N을 2라고 했을때, 처음 0이 오는 경우 그뒤에는 0 또는 1이 올수 있고, 처음 1이 오는 경우 그 뒤에는 0만 올수 있지만 처음이 1인 경우만 출력합니다. (ans = 1)
3. N을 3이라고 했을때, 처음 0이 오는 경우 그 뒤에 0 또는 1이 올수 있고, 처음 1이 오는 경우 그 뒤에는 0만 올수 있지만 처음이 1인 경우만 출력합니다. (ans = 2)
4. N을 4라고 했을때, 처음 0이 오는 경우 그 뒤에 0 또는 1이 올수 있고, 처음 1이 오는 경우 그 뒤에는 0만 올수 있지만 처음이 1인 경우만 출력합니다. (ans = 3)
5. 따라서 N에 대해서 처음 0이 오는 경우는 A[N][0]=A[N-1][0]+A[N-1][1]이 되고 처음 1이 오는 경우는 A[N][1]=A[N-1][0]이 됩니다. 여기서 A[N][1]을 출력하면 답이 됩니다.