[백준] 2193 - 이친수, C++

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

2193번: 이친수

 본 문제는 0과 1로만 이루어진 수 중, 0으로 시작하지 않고, 1이 두 번 연속으로 나타나지 않는 수를 구하는 문제다. 큰 문제를 작은 문제에서 구할 수 있기 때문에 DP로 풀었다. i자리 수 중 0으로 끝나는 수는 i-1자리 수 중 0으로 끝나는 수와 1로 끝나는 수의 합으로 이루어 진다. 따라서, d[i][0] = d[i-1][0] + d[i-1][1]의 점화식이 정의되고 d[i][1] = d[i-1][0]경우를 따로 계산하면 된다.

1. d[i][0] = d[i-1][0] + d[i-1][1]
2. d[i][1] = d[i-1][0]
3. d[n][1] + d[n][0]의 결과 출력

Top-down

#include <cstdio>
#include <cstring>
 
using namespace std;
 
long long d[91][2];
 
long long cal(int n, int i) {
    if (n == 1) {
        if (i == 0) return 0;
        else return 1;
    }
    if (d[n][i] != -1) return d[n][i];
    if (i == 0) d[n][i] = cal(n-1, 0) + cal(n-1, 1);
    if (i == 1) d[n][i] = cal(n-1, 0);
    return d[n][i];
}
 
int main() {
    int n;
    scanf("%d", &n);
    memset(d, -1, sizeof(d));
    long long ans = cal(n, 0) + cal(n, 1);
    printf("%lld", ans);
}

 

Bottom-up

#include <cstdio>
 
using namespace std;
 
long long d[91][2];
 
int main() {
    int n;
    scanf("%d", &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];
    }
    printf("%lld", d[n][0] + d[n][1]);
}