[백준 / BOJ] - 1904번 01타일 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [1904] 

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

문제

 

 

 

풀이

 

규칙성을 찾는것이 중요한 문제이다.

결국 계산을 해보면,

 

N = 3 일때

001, ( N1)

100, 111 (N2)

3개 (N1 + N2)

 

N = 4 일때

0000, 0011, (N2)

1001, (N1)

1100, 1111 (N2)

5개 (N2+N3)

 

N = 5 일때

00001, 00100, 00111 (N3)

10000 , 10011 (N2)

11001, (N1)

11100, 11111 (N2)

8개 (N3 + N4)

 

피보나치 수열을 따른다는것을 알 수 있다.

이를 통해 DP로 풀이를 진행해야 하는데, 피보나치 수열의 값이 매우 커지므로 long long타입으로 데이터를 표현해야하며,

1000000번째 피보나치 수는 long long 타입의 최대값 또한 크게 넘어서므로, 15746 나머지연산을 미리 진행하고 풀이를 진행한다.

 

코드

 

#include <cstdio>
#include <vector>
using namespace std;
int N;
vector<long long> answer = {0,1,2};
void find_answer()
{
    long long tmp;
    for(int i = 3; i <= N; i++)
    {
        tmp = 0;
        tmp = answer[i - 1] + answer[i - 2];
        answer.push_back(tmp%15746);
    }
}
int main() {
    scanf("%d",&N);
    find_answer();
    printf("%lld",answer[N]%15746);
}

 

 

평가

 

피보나치 규칙성을 찾아내는 것이 중요한 문제이며, long long 타입으로도 감당이 되지 않는 큰 숫자를 커버하기 위해 미리 15746 나머지연산을 수행해야한다.