[동적계획법, 난이도 중하] 백준 2193번 이친수

문제에 주어진 조건은 2가지이다.

1. 첫 번째 자리는 0이 될 수 없다.

2. 1이 두 번 연속으로 나타날 수 없다.

 

이 말은 n-1번째 자리가 0이라면 n번째 자리에는 0과1이 모두 올 수 있고

n-1번째 자리가 1이라면 n번째 자리에는 0만 올 수 있다는 것이다.

 

0은 첫 번째 자리 외엔 어느 자리에나 올 수 있으므로

n번째 자리가 0인 경우의 수는 n-1번째 자리가 0인 경우의 수와 n-1번재 자리가 1인 경우의 수의 합

1은 n-1번째 자리가 0인 경우에만 올 수 있으므로

n번째 자리가 1인 경우의 수는 n-1번째 자리가 0인 경우의 수

 

각 자리수의 두 경우의 수를 합한 결과가 이 문제의 답이다.

 

이를 표로 정리하면 이렇다.

(예시로 n=7까지 작성)

예제 입력1) n=3인 경우 답은 2+1=3

 

 

#include <iostream>
using namespace std;
long long save[91][2];
int main() {
	int n;
	cin >> n;
	save[1][0] = 0;
	save[1][1] = 1;
	save[2][0] = 1;
	save[2][1] = 0;
	for (int i = 3; i < n + 1; i++) {
		save[i][0] = save[i - 1][0] + save[i - 1][1];
		save[i][1] = save[i - 1][0];
	}
		cout << save[n][0] + save[n][1] << endl;
}