[백준 2193번] 이친수 (C++)

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

2193번: 이친수

---

이친수 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 

다이나믹 프로그래밍은 테이블 정의, 점화식 작성, 초기값 정하기의 과정으로 구분할 수 있습니다.

1. 테이블 정의
   • 이친수에서는 1이 연속으로 나타나지 않는다는 조건이 있기 때문에 0과 1을 구분할 필요가 있습니다.
   • 이진수는 0또는 1로 끝날 수 있으므로, d[i][j]은 i자리이고, j로 끝나는 이친수의 개수라고 정의하였습니다.
   • 예를 들어 d[3][1]은 3자리이고, 1로 끝나는 이친수의 개수입니다. (ex. 101)
2. 점화식 작성
   • n자리 이친수는 n - 1자리의 이친수의 끝에 0 또는 1을 붙여 만들 수 있습니다.
   • 하지만, 1이 두 번 연속으로 나타나지 않으므로, 1로 끝나는 n - 1자리의 이친수의 끝에는 1을 붙일 수 없습니다.
   • 따라서, 점화식은 아래와 같습니다

// i자리의 0으로 끝나는 이친수의 개수 = (i - 1)자리의 0으로 끝나는 이친수의 개수 + (i - 1)자리의 1으로 끝나는 이친수의 개수
d[i][0] = d[i - 1][0] + d[i - 1][1] 
// i자리의 1으로 끝나는 이친수의 개수 = (i - 1)자리의 0으로 끝나는 이친수의 개수
d[i][1] = d[i - 1[0];

 

아래는 전체 코드입니다.

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

long long d[100][2]; // d[i][j]는 i자리이고, 끝자리가 j인 이친수의 개수
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    d[1][0] = 0; d[1][1] = 1;   // 초기값 정하기
    
    for(int i = 2; i <= n; i++){    // 테이블 채우기
        d[i][0] = d[i - 1][0] + d[i - 1][1];
        d[i][1] = d[i - 1][0];
    }

    cout << d[n][0] + d[n][1];
}