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

2193번: 이친수 (acmicpc.net)

2193번: 이친수

---

규칙을 알아봅시당

 

 1로 시작하고 11이 나오면 안되므로

아이디어 1) n>1 일 때는 10_ 으로 시작해야한다

아이디어 2)  조합을 생각했을 때, 10 다음부터는 0,1로 채워지되 1만 연속하게 안나오게 만들면 됨

ex) T(5) = 2^4 - 6 = 10

T(6) = 2^5 - 10 = 22

 

n=1일 때, 1가지 (1)

n=2일 때, 1가지 (10)

n=3일 때, 2가지 (10_: 100, 101)

n=4일 때, 3가지 (10__ : 1000/ 1001, 1010) 1+2

n=5일 때, 5가지 (10___: 10000 / 10001, 10010, 10100 /  10101) 1+3+1

n=6일 때, 10가지 (10____: 100000 / 100001, 100010, 100100, 101000 / 10 ) 1+4+

n=7일 때, 22가지

n=8일 때, 49가지

 

T(n) = 2^(n-2) - (1부터 n-1까지의 합)

이라고 생각했는 데

?????????????

어라라 제대로 헛발질

생각해보니 10_ 이후로만 조합을 생각해줌

---

 

n=1일 때, 1가지 (1)

n=2일 때, 1가지 (10)

n=3일 때, 2가지 (10_: 100, 101)

n=4일 때, 3가지 (10__ : 1000/ 1001, 1010) 1+2

n=5일 때, 5가지 (10___: 000 / 001, 010, 100 /  101) 1+3+1

n=6일 때, 8가지 (10____: 0000 / 0001, 0010, 0100, 1000 / 0101, 1010, 1001 ) 1+4+3

 

백준 2193 이친수 c++ (dp) (tistory.com)

백준 2193 이친수 c++ (dp)

네.. 점화식이 

n=1,2 일 때) T(n) = 1

n이 3이상일 때)T(n) = T(n-1) + T(n-2)

인 간단한 식이었다는 거..! 

코드로 표현합시당

---

계속 틀려서 위에 링크 코드를 참고 했는데, 

int 대신에 long long 타입으로 선언해줘야 했다

바꿔주니 성공!

#include <iostream>
using namespace std;

int main()
{
    int x;
    cin >> x;
    
    if(x == 1 ||  x == 2) {
        cout << 1 << "\n";
        return 0;
    }
    
    long long arr[x+1] = {0, 1, 1, };
 
    for(int i=3; i<=x; i++){
        arr[i] = arr[i-1] + arr[i-2];
    }
    
    cout << arr[x] << "\n";
    
    return 0;
}