[BaekJoon 1904번] 01타일(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

 

[문제 풀이 사이트]

 

 

1904번: 01타일

 

 

[문제 설명]

 

 

지원이에게 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으로 나눈 나머지를 출력한다.

 

 

[입출력 예]

 

 

입력	출력
4	5

 

 

[문제 풀이]

 

 

DP 문제이다. 쉽게 풀었다.

 

1. 테이블을 정의한다.

 

dp[n] = 지원이가 1과 00으로 만들 수 있는 길이가 n인 모든 2진 수열의 개수

 

 

2. 점화식을 정의한다.

 

길이(n)가 1에서 5까지 만들 수 있는 2진 수열을 아래와 같이 표로 정리해보았다.

길이가 n일 때 만들 수 있는 2진 수열
n = 1 (1개)	n = 2 (2개)	n = 3 (3개)	n = 4 (5개)	n = 5 (8개)
1	11 00	111 001 100	1111 1001 0011 1100 0000	11111 10011 00111 11001 00001 11100 10000 00100

 

점화식을 찾아보자.

 

길이(n)가 3일 때를 보면

111

001

길이(n)이 2일 때의 방법에 1을 붙임

 

100

길이(n)이 1일 때의 방법에 00을 붙임

 

여기서 점화식에 대한 확신을 얻기 어려우니 ..

길이(n)가 4일 때도 해보자!

1111

1001

0011

길이(n)이 3일 때의 방법에 1을 붙임

 

1100

0000

길이(n)이 2일 때의 방법에 00을 붙임

 

위 내용으로 보아 점화식을 아래와 같이 정의할 수 있다.

dp[n] = dp[n - 1] + dp[n-2]

 

 

3. 초기값을 정의한다.

 

초기값은 dp[1] = 1, dp[2] = 2 로 정할 수 있다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
#define MODULAR 15746

using namespace std;
using ull = unsigned long long;

vector<ull> dp;

ull binarySequence(int n) {
    if(dp[n] != 0) return dp[n];
    else {
        return dp[n] = (binarySequence(n -1) + binarySequence(n -2)) % MODULAR;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; 
    cin >> N;
    dp.resize(N + 1);
    dp[1] = 1; dp[2] = 2;
    binarySequence(N);
    cout << dp[N];
    return 0;
}