baekjoon - (01타일)

문제 번호 : 1904번

난이도 : Silver 3

시간 제한메모리

0.75 초 (추가 시간 없음)

256 MB

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

 

예제 입력 1

4

예제 출력 1

5

 

풀이) 

이 문제는 0.75 초라는 시간 제한으로 최대 1,000,000개의 자연수가 주어졌다라고 하면 타일의 경우의 수를 재귀 함수나 다른 알고리즘으로 풀었을 경우 시간 초과가 난다. 그러면 다이나믹프로그래밍으로 접근해보면 결국 타일은 00과 1을 통해서 점화식을 세울 수 있고, O(n)만큼 돌기 때문에 시간제한에 걸리지 않게 된다.

 

먼저 간단하게 

1이라는 수가 들어왔을 때 우리는 00은 안되니까 1 하나만 들어갈 수 있어서 1개의 경우의 수가 나오게 된다.

2라는 숫자에서는 01은 안되고, 00과 11이 가능하다.

그러면 3이라는 숫자가 들어오면 어떻게 될까? 전에 기록했던 2라는 숫자에서 00, 11에서 1개만 들어올 수 있으니까 1을 붙이면 001, 111이 된다. 그러면 전에 기록했던 1이라는 숫자에서는 1에서 2개를 집어넣을 수 있는데 100이 가능할 것이다. 111도 가능하지만 이미 111은 있기 때문에 100, 111, 001 이라는 3개의 숫자가 나온다.

 

그러면 여기서 점화식을 세울 수 있다.

현재 n번의 번호는 n-1 + n-2  하게 되면 n번의 경우의 수가 나오는구나라는 걸 알 수 있다.

 

코드)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    vector<int> vec(1000001);
    vec[0] = 0;
    vec[1] = 1;
    vec[2] = 2;
    for(int i=3; i<=T; i++){
        vec[i] = vec[i-1]%15746 + vec[i-2]%15746; 
    }
    
    cout << vec[T]%15746;
    return 0;
}