[BOJ/C++]2193번 이천수

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

2193번: 이친수

---

문제

이진수 중

1. 1이 연속으로 들어오지 않고
2. 1로 시작하는 수를

이천수라 한다. 예를들어 1001이나 1010은 이천수지만, 1101이나 10110은 이천수라 할 수 없다.

n자리수(1<=n<=90)의 이천수 개수를 구해라.

 

풀이방법

https://lionontheshore.tistory.com/33?category=929275

[BOJ/C++]10844 번 쉬운 계단 수

와 비슷한 방식으로 풀었다. 다만 이 문제는 올 수 있는 수가 0,1 두 개로 더 간단하게 풀 수 있었다.

i번째에 0이 오는 경우는 i-1번째에서 0인 경우와 1인 경우 두 경우를 더해주었고,

i번째에 1이 오는 경우는 i-1번째에서 0인 경우만 가져왔다.

 

**내가 틀렸던 부분**

처음에 출력하는 정수를

int dp[n+1][2];

로 정의했다. 이 경우 n에 90을 넣었을 때 범위를 초과하므로

long dp[n+1][2];

로 정의해야 한다.

 

 

소스코드

#include<iostream>
using namespace std;

int main(void){
    int n;cin>>n;
    long dp[n+1][2];
    dp[1][0]=1;dp[1][1]=1;
    for(int i=2;i<=n;i++){
        dp[i][0]=dp[i-1][0]+dp[i-1][1];
        dp[i][1]=dp[i-1][0];
    }
    cout<<dp[n][1]<<endl;
}