문제

image.png

image.png

풀이

이차원 다이나믹 프로그래밍 풀이

점화식을 다음과 같이 정의할 수 있다.

dp[n][l] = n 자리 이친수, 마지막 수 l

이친수가 되려면, 이진수 이면서 첫번째 자리에 0이 오면 안되고, 11을 부분 문자열로 가지면 안된다.

dp[n][0] = n자리 이친수, 마지막 수 0

마지막에 0 이 왔으면 그 앞에는 어떤 수 등장해야 될까?

  1. 0 앞에 0 오는 경우
    dp[n-1][0] 가능하다.
  2. 0 앞에 1 오는 경우
    dp[n-1][1] 가능하다.

dp[n][l] = dp[n-1][0] + dp[n-1][1]

마지막에 1이 왔으면 그 앞에 어떤 수 등장해야 할까?
0오는 경우 가능하다, 1오는 경우 불가능 하다.

dp[n][0] = dp[n-1][0]

1차원 다이나믹 프로그래밍 풀이

2193번 문제는, 1차원 dp로도 해결이 가능하다. dp[n] = n자리 이친수 라고 하자
먼저, N에따라서 이친수가 어떻게 구성되는지 알아보면 아래와 같다.

N = 1인 경우, 1
N = 2인 경우, 10
N= 3인 경우, 100,101,101

N=3인 경우를 자세히 살펴보면, (10 + 0), (10 + 1), (1 + 01) 이다. N-1의 이친수와 N-2의 이친수로 구성되어 있는것을 확인할 수 있다. N-1번째 이친수의 끝에 0을 붙이는 경우, N-1번째 이친수의 끝에 1을 붙이는 경우, N-2번째 이친수의 끝에 01을 붙이는 경우로 나눠진다.(01을 붙이는 이유는, 11이 붙으면 이친수 조건이 아니기 때문)


1) 마지막 수 0
dp[n-1]의 끝에 0이 오는 경우 이므로 무조건 이친수 이다.

2) 마지막 수 1
dp[n-1]의 끝에 1이 오는 경우 앞에는 0만 올 수 있다.

...11 (x)
...01(o)

01을 하나로 합쳐서 생각 하면, dp[n-2] 끝에 01이 오는 경우로 생각하면 된다.
n자리 이친수는 마지막에 0이 오거나,1이 오는 경우 이므로 둘을 합치면 된다.

dp[n] = dp[n-1] + dp[n-2]

코드

#include <iostream>
using namespace std;
long long d[91];
int main() {
    int n;
    cin >> n;
    d[1] = 1;
    d[2] = 1;
    for (int i=3; i<=n; i++) {
        d[i] = d[i-1] + d[i-2];
    }
    cout << d[n] << '\n';
    return 0;
}