[Baekjoon] 1904번: 01타일

 

 

 

https://www.acmicpc.net/problem/1904

1904번: 01타일

 

---

 

문제 해결 과정

착안

처음에는 문제를 해결할 마땅한 방법이 잘 안떠올라서 모든 가능한 문자열을 실제로 전부 구해보고(브루트 포스, 무차별 대입) 길이가 $N$이 될 때 Count를 하나씩 늘리는 방식으로 프로그래밍 했는데, 문자열이 길어짐에 따라 분기가 크게 늘어나므로 너무 많은 수의 재귀 호출이 일어나 메모리 초과로 실패했다. 이런 상황을 어떻게 해결할지 한참 고민하다가 아래와 같이 단계를 나누고, 단계별 결과 사이에 어떤 관계가 성립하는지를 살펴보고자 하였다.

 

한 번에 타일 하나를 사용하여 문자열을 늘려간다고 했을 때 길이가 $N$인 문자열을 만들기 위해서는, 이전 단계의 문자열의 길이가 반드시 $N-1$ 또는 $N-2$여야 한다(타일이 '1', '00' 밖에 없으므로 붙일 수 있는 길이는 1 또는 2 이므로).

 

• 이전 단계의 문자열 길이가 $N-1$일 때: 타일 '1'을 추가하는 경우 $\longrightarrow$ 1 가지
• 이전 단계의 문자열 길이가 $N-2$일 때: 타일 '00'을 추가하는 경우 $\longrightarrow$ 1 가지
• 이전 단계의 문자열 길이가 $N-1$ 또는 $N-2$가 아닌 경우: 타일 하나로는 불가능, 또는 문자열 길이 초과

* 참고) 길이가 $N-2$인 문자열에서 타일 '1'을 이용하여 길이를 $N$으로 만들려면 타일이 두 개 사용된다.

 

 

따라서 길이가 $N$인 문자열을 만드는 방법의 수를 $f(N)$이라고 할 때, 위를 식으로 나타내면 $N > 2$일 때,

$$f(N) = f(N-1) \times 1 + f(N-2) \times 1 = f(N-1) + f(N-2)$$

이므로 $f(N)$은 처음 두 항을 1, 2로 하는 피보나치 수열(Fibonacci sequence)의 $N$번째 항이다. 따라서 해당 피보나치 수열의 $N$번째 항을 동적계획법(dynamic programming)을 통해 구하여 문제를 해결하고자 하였다.

 

한편, 구하고자 하는 경우의 수를 15746으로 나눈 나머지를 출력해야 하는데 이때 나머지 연산(modulo operation)의 특성에 의하여 임의의 정수 $n_1, n_2, m$에 대해 $(n_1 + n_2)$을 $m$으로 나눈 나머지는 $n_1$을 $m$으로 나눈 나머지와 $n_2$을 $m$으로 나눈 나머지를 더한 값을 $m$ 으로 나눈 나머지와 같음을 활용하였다.

* 나머지 연산과 관련된 산술 체계를 모듈러 산술(modular arithmetic)이라고 한다.

 

구현

처음 두 항이 1, 2임에 주의하여 피보나치 수열을 동적계획법을 사용하여 계산할 수 있도록 프로그래밍하였다. 이때, $N$이 비교적 큰 숫자가 될 수 있기 때문에 배열을 사용한 메모이제이션으로는 배열 크기가 너무 커질 수 있기 때문에 메모리를 많이 사용하게 되므로 상향식(bottom-up) 동적계획법에서 $N-1, N-2$번째 피보나치 수만을 메모이제이션 하여 메모리를 절약해보았다.

* 참고) 이전에 계산한 값들을 다음 번째의 피보나치 수를 구할 때 외에는 딱히 재사용하지 않기 때문에 가능한 방법이다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int FindWord(int n)
{
	if (n < 2)
		return 1;

	int a = 1, b = 1;
	for (int i = 2; i < n + 1; i++)
	{
		int temp = (a + b) % 15746;
		a = b;
		b = temp;
	}

	return b;
}

int main()
{
	int N;
	cin >> N;
	cout << FindWord(N) << "\n";
	return 0;
}

 

실행 결과

 

아래의 결과부터 순서대로,

 

1. 브루트 포스 알고리즘으로 시도한 결과
2. 단순 오타 (15746으로 나누어야 하는데 15476으로 나눔;)
3. 하향식 동적계획법, 1000001 개의 요소를 가지는 배열을 사용한 결과
4. 상향식 동적계획법, int형 변수 3 개만 사용하여 메모이제이션을 활용한 결과

 

이다. 배열을 사용하지 않았더니 메모리 절약과 동시에 실행 속도 향상이 있었다.