[백준/BOJ] 1904번: 01 타일 (동적 계획법) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/1904

 

풀이

숫자 N이 주어졌을 때,  N 자릿수의 2진법 숫자를 만들 수 있는 개수를 알아내는 문제이다.

 

문자를 읽어보면, 0000을 0으로 생각하는 것이 아니라 네 자리 숫자로 계산해야 된다.

이렇게 되면 1과 0으로 만들 수 있는 숫자의 수는 2ⁿ이다.

 

이전의 만들어진 숫자에 1 또는 0을 붙이면 되기 때문이다.

이를 식으로 쓰면 

F(N) = F(N-1) * 2 = F(N-1) + F(N-1)

이 된다.

여기서 F(N)은 타일을 가지고 만들 수 있는 N 자릿수의 숫자의 개수이다.

 

그런데, 이 문제에서는 0 대신 00 카드를 사용해야 한다.

00 카드를 써서 N 자릿수 숫자를 만들려면 N-2 자릿수 숫자에 00 카드를 붙여야 된다.

 

그럼 위 식은 다음과 같이 바꿀 수 있다

F(N) = F(N-1) + F(N-2)

 

이 문제는 재귀 함수를 작성하면 너무 간단하지만, N이 커질수록 수행 시간이 기하급수적으로 늘어난다.

동적 계획법을 사용해야 한다.

 

동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후, 이 계산한 결과를 사용하여 전체의 문제를 빠르게 푸는 방법이다.

 

버퍼를 마련해서 이전 계산 값을 저장하고, 필요할 때 재사용하는 방식이다.

위의 식을 코드로 바꾸면 아래와 같이 된다.

#define NUM 1000000
int cache[NUM];

cache[1] = 1;	// 타일로 만들 수 있는 1자리수 숫자의 갯수
cache[2] = 2;	// 2자리수 숫자의 갯수 ( 11과 00 )

for(int i = 3; i <= N; i++){
    cache[i] = (cache[i-1] + cache[i-2]);
}

 

해결해야 할 문제가 하나 더 있다. 

N이 커질수록 F(N)의 값은 기하급수적으로 커진다는 것이다. 

N이 30만 넘어도 F(N)은 백만이 넘기 때문에 버퍼에 담을 때 문제가 생긴다.

 

출제된 문제에서도 이 부분을 인지하고 15746으로 나눈 결과 값을 출력하도록 요구하고 있다.

하지만 출력 값만 나머지 값을 구하는 것으로는 부족하고, 모든 중간 값에 대해서도 나머지 값을 구해야 int의 범위를 넘지 않는다.

 

수학의 힘을 빌릴 때가 왔다.

C = A + B의 경우 ( A, B, C, D는 정수 )

C mod D = (A+B) mod D = (A mod D + B mod D) mod D

 

이고, 이를 사용하면 모든 결과 값이 15746을 넘어가지 않도록 제한을 만들 수 있다.

 

#define NUM 1000000
int cache[NUM];

cache[1] = 1;	// 타일로 만들 수 있는 1자리수 숫자의 갯수
cache[2] = 2;	// 2자리수 숫자의 갯수 ( 11과 00 )

for(int i = 3; i <= N; i++){
    cache[i] = (cache[i-1] + cache[i-2]) % 15746;	// 15746을 넘지 않도록
}

 

 

소스 코드

#include <iostream>
using namespace std;

#define NUM 1000000
int cache[NUM];

int main(){

    int N;
    cin >> N;

    cache[1] = 1;
    cache[2] = 2;

    for(int i = 3; i <= N; i++){
        cache[i] = (cache[i-1] + cache[i-2]) % 15746;
    }

    cout << cache[N];

    return 0;
}