2193 이친수

풀이코드

#include <iostream>
#include <cstdio>
using namespace std;
// 2193

int main(){
	long long dp[91][2] ={0};
	int length;
	
	cin >> length;	
	
	dp[1][1] = 1;
	
	for(int i = 2; i <= length; i++){
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][1] = dp[i - 1][0];
	}
	
	cout << dp[length][0] + dp[length][1] << endl;
	
}

 

해설

이전의 계단 수 문제들과 마찬가지로 n 번째와 n - 1 번째와의 관계를 파악하는 것이 중요했다. 끝 자리 수가 0 이려면 그 앞자리 수는 0이거나 1이여야 하고, 끝 자리수가 1 이려면 그 앞자리 수는 무조건 0 이여야 한다는 것이다.

한번에 맞추지 못하고 틀렸었는데 그것은 int 범위를 벗어난 답이 도출 되었기 때문이다. 그래서 dp 를 long long 자료형으로 바꾸어 문제를 해결했다.