[백준/BOJ] 1904번 01타일 (C/C++)

백준 온라인 저지(BOJ) 1904번 01타일
https://www.acmicpc.net/problem/1904

1904번: 01타일

* 사용언어 : C언어, C++
 

1. 문제

1 하나로 이루어진 타일 또는 0타일 두 개를 붙인 00타일로 만들 수 있는 크기가 N인 타일(2진 수열)의 개수를 출력
N은 최대 1,000,000이고, 출력은 수열의 개수를 15,746으로 나눈 나머지로 출력

 

2. 풀이

단순 재귀로 구현하면 시간 초과가 발생합니다.
동적 계획법에 속하는 문제인 만큼 dp[] 배열을 선언한 후 값을 저장하면서 풀어줍니다.
 
다만 이 문제는 00 또는 1 타일을 하나 씩 배치하면서 개수를 세는 백트래킹 방식으로 구현한다면,
dp 배열을 활용하더라도  시간 초과가 발생하게 됩니다.
 
정리해서 다시 말하면 top-down 방식으로는 풀 수 없는 문제입니다.
 
 
bottom-up 방식으로 문제를 풀기 위해서는 수열의 개수가 증가하는 규칙을 찾아야 합니다.
특별한 규칙이 보이지 않아서 1부터 5까지 가능한 모든 2진 수열을 직접 적어보며 규칙을 찾아보았습니다.

N = 1 ~ 5까지 모든 2진 수열 및 출력 값 (개수)

 
우선 N = 1이거나 2일 때는 특별한 규칙이 없습니다.
 
N = 3일 때를 보면 맨 앞 자리에 00 또는 1을 배치할 수 있는데
00을 배치한 경우 1자리(3 - 2)가 남기 때문에 N = 1일 때의 경우와 같고,
1을 배치한 경우 2자리(3 - 1)가 남기 때문에 N = 2일 때의 경우와 같아집니다.
 
여기서 규칙을 바로 찾을 수 있었습니다.
N = n일 때 가능한 모든 2진 수열의 개수는 [N = n - 2일 때의 개수] + [N = n - 1일 때의 개수]였습니다.
 
다시 말하면 피보나치 수열과 같은 방식으로 구현할 수 있다는 것을 확인할 수 있었습니다.
(단, 피보나치 수열은 N이 2일 때의 값도 1이므로 결과값은 다릅니다.)
 
 
추가로 나머지 연산(% 모듈러)을 미리 해주지 않으면 값이 매우 커져서 오답이 됩니다.
나머지 연산은 분배 법칙이 가능하기 때문에 dp 배열에 넣을 때 미리 나머지 연산을 하여 기록했습니다.
 
모듈러 연산을 매 번 하기 때문에 dp배열에 입력되는 최대값은 2^15보다 작아집니다.
따라서 dp 배열을 int가 아닌 short로 선언하여 메모리 사용량도 줄일 수 있었습니다. (5,016KB → 3,064KB)
 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1904_01타일
3064KB	4ms
*/
#include <cstdio>

const int LM = 1e6 + 1;
const int BASE = 15746;
int N, cnt;
short dp[LM];

void tile(int n) {
	dp[1] = 1, dp[2] = 2;
	for (int i = 3; i <= n; ++i) dp[i] = (dp[i - 1] + dp[i - 2]) % BASE;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	tile(N);
	printf("%d\n", dp[N]);
	return 0;
}