[백준(BOJ)] 2193번: 이친수 (Dynamic Programming, C++)

✔ 문제설명

---

• 이진수: 0과 1로만 이루어진 수
• 이친수(pinary number): 이진수 중 특별한 성질 가진 수
  1. 0으로 시작하지 않는다.
  2. 1이 두 번 연속 나타나지 않는다. 11을 부분 문자열로 가지지 않는다.
• 이친수 예: 1, 10, 101, 1000, 1001 등

 

📝 문제풀이 과정

---

• DP[i][j]: i번째 자리에서 j가 오는 경우 (j는 0 또는 1)
• N자리 일 때, N == 1이면 DP[1][1] = 1, DP[1][0] = 0 
  • 1만 가능하므로 1일 때는 1로 카운팅, 0일 때는 0으로 카운팅한다.
• if(j == 1) DP[i][j] = DP[i-1][0]
  • 현재 수가 1인 경우, 앞은 0만 올 수 있다.
• else if(j == 0) DP[i][j] = DP[i-1][0] + DP[i-1][1]
  • 현재 수가 0인 경우, 앞은 1 또는 0이 올 수 있다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>
int main(){
    int N;
    scanf("%d", &N);

    long long  DP[N+1][2] = {0,}; // N == 90인 경우, 수가 크므로 long long 형
    
    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]; // 0일 때 1 또는 0이 오면 됨
        DP[i][1] = DP[i-1][0]; //1일 때 앞에는 항상 0이 와야 함
    }
    
    printf("%lld", DP[N][0] + DP[N][1]);
}

 

 

👏 결과

---