백준 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이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

 

---

00 과 1 의 타일을 이용해서 n개의 자릿수를 가진 이진수를 만드는 그런문제!

 

먼가 정해진 규칙이 있을것 같은데 바로는 몰라봐서 조금 구해봤습니다.

 

타일 갯수를 n 이라 할때 dp[n] 에 각각 저장해주었습니다.

 

 

 

dp[0]=0

dp[1]=1

dp[2]=2

dp[3]=3

dp[4]=5

dp[5]=8

dp[6]=13

dp[7]=21

 

 

대충 여기까지 구해보니까 보이네요;;

 

0~2 까지는 정해주고 나머지는

 

dp[i]=dp[i - 1] + dp[i - 2]; 의 규칙을 가집니다!

빨리알아차렸어야했는데;;

 

 

여기까지 아라내셨다면 코드는 어렵지 않습니다

 

 

long long 형의 배열에 아래처럼 미리 계산해주고

long long dp[1000001]={0};

void cal() {
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;

    long long memo;
    for (int i = 3; i < 1000001; i++) {
        memo = 0;
        memo = dp[i - 1] + dp[i - 2];
        dp[i] = memo % 15746;
    }
}

 

dp[n] 을 출력해줍시다.

int main() {
    int num;
    cal();


    scanf("%d",&num);
    printf("%lld", dp[num]);
}

 

끝!

 

 

 

#include <iostream>
#pragma warning(disable:4996)
using namespace std;

//dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=2, dp[4]=5, dp[5]=8
// 0 1 2 3 5 8 13 21 

long long dp[1000001]={0};

void cal() {
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;

    long long memo;
    for (int i = 3; i < 1000001; i++) {
        memo = 0;
        memo = dp[i - 1] + dp[i - 2];
        dp[i] = memo % 15746;
    }
}

int main() {
    int num;
    cal();


    scanf("%d",&num);
    printf("%lld", dp[num]);
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!