[백준 C++] 2193번: 이친수

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

2193번: 이친수

일단 dp로 문제를 해결해야하고 본 순간 1로 끝나는 배열과 0으로 끝나는 배열의 갯수를 따로 저장해야될꺼같다는 생각이 들었다. 왜냐면 0으로 끝나는 이전 dp[i-1]배열은 다음 수로 0과 1이 모두 들어갈 수 있지만, 1로 끝나는 이전 dp[i-1]배열은 0밬에 못들어가기 때문이다.

 

따라서 식을 작성해보면 

dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][1] = dp[i - 1][0];

이렇게 표현 가능하다. 

 

또 하나 주의해야 할 점은 dp를 int형으로 선언하게 된다면 n의 값이 커질때 결과값을 받아 낼 수 없으므로 long long형으로 선언해주도록 하자.

 

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[91][2] = { 0, };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	dp[1][1] = 1;
	dp[2][0] = 1;
 
	int n;
	cin >> n;
 
	for (int i = 3;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] << "\n";
	
	return 0;
}

 

새로운 개념인 dp 문제중에 가장 최단시간으로 풀었던 문제이다. 뿌듯하다.