[BOJ] 백준 2193번: 이친수

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

2193번: 이친수

 

이번에도 DP 기본 문제입니다.

 

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

int N;
ll dp[91][2];

void solve(){
	dp[1][0] = 0;
	dp[1][1] = 1;
	
	for(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][0] + dp[N][1];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	solve();
}

 

항상 같은 패턴입니다. dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 풀이합니다.

 

1) table 정의

dp[i][k] : k로 끝나는 i자리 이친수의 개수(k = 0, 1)

 

2) 점화식 찾기

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

 

3) 초기값 설정
dp[1][0] = 0;
dp[1][1] = 1;

 

이친수에서는 1이 두 번 연속으로 나타나지 않는다는 제약 조건으로 인해 2차원 table을 정의하여 점화식을 세웠고,

이친수는 0으로 시작하지 않는다는 성질은 초기값 설정에서 dp[1][0] = 0 으로 설정해주면 만족하게 됩니다.

 

주의할 점은 N이 90으로 작더라도 90자리 이친수의 개수는 2880067194370816120개로 매우 많습니다.

dp 배열의 자료형을 int로 할 경우 integer overflow가 발생하므로 잘못된 답을 출력하게 됩니다.

꼭 경계조건 등 코너 케이스에 유의하여 미리 임의의 테스트케이스를 만들어 값을 넣어볼 필요가 있습니다.

이 문제의 경우 최악의 경우에도 이친수의 개수가 long long의 범위 안에 있으므로 long long 자료형을 사용하면 되지만, 종종 long long 의 범위를 넘어가는 문제가 있는데 그럴 때에는 string이나 vector를 이용해 큰 수(big integer)의 연산을 구현해야 합니다. 다만 이런 경우에는 대부분 문제에서 주어진 값으로 나눈 나머지를 출력하도록 문제가 구성됩니다.

 

시간복잡도는 O(N)입니다.