백준 1904번 - 다이나믹 프로그래밍

 

지원이에게 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. 생각

가능한 경우를 모두 적다보면 규칙을 발견할 수 있다. 바로 이전 두개의 합이 그 다음의 수가 된다는 것이다.

이를 확인하기 위해 경우의 수를 나열해보면 다음과 같다. 

첫번째에서는 뒤에 00을 더하고, 두번째에서는 뒤에 1을 더한다면, 그 다음 구하는 경우의 수의 집합이 된다 .

 

따라서 f(i ) = f(i-1) + f(i-1) , 즉 피보나치 꼴과 같은 값이 된다. 

 

 

 

그러나 여기서 N의 제한은 1,0000000이하이므로, 오버플로우의 위험이 있다.

그래서 처음에는 unsigned long long으로 저장을 하다가, 그래도 되지 않자 15746으로 나눈 나머지 자체를 저장하였다. 

다이나믹 프로그래밍을 하는 것에 있어 문제에서 요구하는 대로 원하는 값을 더 쉽고 빠르게 구하려면 처음부터 이렇게 설계하는 게 더 좋았다는 생각이 든다. 

 

 

 

2. 구현

 

 

내가 짠 코드는 다음과 같다. 

#include <stdio.h>
#include <string.h>

unsigned long long answer[1000001];
int N;
void init()
{
    answer[1] = 1;
    answer[2] = 2;
    for(int i =3;i<=N;i++)
    {
        answer[i] = (answer[i-1] + answer[i-2])%15746;
        //printf("%llu ", answer[i]);
    }
}

int main()
{
    scanf("%d", &N);
    init();
    printf("%llu", answer[N);

}