[백준] 1904.cpp : 01타일

www.acmicpc.net/problem/1904

1904번: 01타일

---

• N 자릿수에 가능한 갯수 = (N - 1 자릿수의 수들에 1 을 붙인 수 (x1)) + (N - 2 자릿수의 수들에 00 을 붙인 수 (x1))

---

#include <iostream>

using namespace std;

int n;
int num[1000001] = {0, 1, 2, 3, 5};

int main(void)
{
    cin >> n;
    for(int i = 5 ; i <= n ; i++)
    {
        num[i] = ((num[i-1] % 15746) + (num[i-2] % 15746)) % 16746;
        // i-2 자리에 00 이 붙을 수 있고, i-1 자리에 1 이 붙을 수 있기 때문에 피보나치 수열과 같음
        // 모듈러 연산의 특성에 의하여 나머지 연산을 매번 해줌
    }
    cout << num[n] << endl;
}

---

• 2등 소스코드 참고 : www.acmicpc.net/source/19854316
• 배열 100만개를 매번 다 사용하지 않으니, 실제로 반복 때 사용할 공간 3개만 재활용하면서 반복한다.
• 어차피 매번 15746 보다 작은 수로 바꿔줄 것이기 때문에, 두 수를 더한다고 하더라도 15746 을 한번만 빼줘도 된다.

---

#include <stdio.h>
int N, a[3];
int main(int argc, char* argv[])
{
    scanf("%d", &N);

    a[0] = 1;
    a[1] = 1;
    for(int i = 2 ; i <= N ; i++)
    {
        a[2] = a[0] + a[1];
        if(a[2] >= 15746) a[2] -= 15746;
        a[0] = a[1];
        a[1] = a[2];
    }
    printf("%d", a[1]);
}