[백준/C++] 2193번_이친수

문제는 다음과 같습니다.

먼저 구해야하는 문제의 초항(초기 세팅)은 다음과 같습니다.

자리수가 하나일 경우는 1만 가능=> 1
자리수가 두자리일 경우는 10만 가능=> 1
자리수가 세자리일 경우는 100, 101 가능 => 2

이렇게 나아갑니다.

그리고 저는 바로 점화식의 조건이 보였는데요.
가장 중요한 조건은 "1이 두 번 연속으로 나타나지 않는다"인 것 같습니다

즉 n자리인 어떤 수가 있다고 가정했을 때,

이 수는 다음 두 가지 경우 중 하나입니다.

• (.....)0 => 마지막이 0으로 끝나는 경우
• (....)01 => 마지막이 1로 끝나는 경우

• 첫 번째 경우는, 마지막이 0으로 끝나는 경우입니다.
  이때에 나올 수 있는 개수는 a(n-1)입니다.

• 두 번째 경우는, 마지막이 1로 끝나는 경우입니다.
  이때에는 1전의 수는 반드시 0이어야 합니다.
  즉, 이때 나올 수 있는 개수는 맨 뒤의 두자리 0,1 을 제외한 a(n-2)입니다.

즉 점화식은 다음과 같습니다.
n자리 수의 이친수의 개수 a(n)은,

a(n) = a(n-1) + a(n-2)

전체 코드는 다음과 같습니다.

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

long long d[91]={0, };

long long func(int num){
  if(d[num]) return d[num];

  else return d[num]=func(num-1)+func(num-2); 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    d[1]=1; d[2]=1; // 초기 조건 세팅
    int n;
    cin>>n;
    cout<<func(n)<<endl;
    return 0;
}

---

2월 8일 화요일 복습)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long dp[91][2]={0, }; int n; cin>>n;
    dp[1][0]=0; dp[1][1]=1;

    for(int i=2; i<=n; i++){
      for(int j=1; j>=0; j--){
        if(j==1) dp[i][j] = dp[i-1][0]; // 1은 연속 2번 x
        else dp[i][j] = (dp[i-1][0]+dp[i-1][1]);
      }
    }

    cout<<dp[n][0]+dp[n][1]<<"\n";
    return 0;
}

2차원 배열 dp[i][j]에서 i=idx(인덱스)+1을 나타내고 <해당 자리>,
j=자리에 해당하는 값을 의미합니다.