[백준 / C++] 2193번: 이친수 (dp, 다이나믹 프로그래밍)

https://www.acmicpc.net/problem/2193

2193번: 이친수

난이도: solved.ac 실버 3

 

알고리즘 분류

다이나믹 프로그래밍 (dp)

 

접근 방법

0은 여러개 이어져도 상관없다.

1은 2개 이상 연속되면 안 된다.

 

따라서 0 이전의 숫자는 0 또는 1이 가능하고, 1 이전의 숫자는 0만 가능하다.

 

그럼 점화식은 아래와 같이 나타낼 수 있다.

n번째 숫자가 0인 경우의 수: dp[n][0] = dp[n-1][0] + dp[n-1][1]

n번째 숫자가 1인 경우의 수: dp[n][1] = dp[n-1][0]

 

코드

#include <bits/stdc++.h>
using namespace std;

long long dp[91][2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, i;
	cin >> N;
	dp[1][1] = 1;
	for (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][0] + dp[N][1];
}

 

코드 제출 결과