백준 알고리즘 1904번: 01타일 [C++]

문제 출처: www.acmicpc.net/problem/1904

1904번: 01타일

1. 코드

#include <iostream>

using namespace std;

int arr[1000001] = { 0, 1, 2 };

int solution(int n)
{
	if (n == 0) return 0;
	else if (n == 1)return 1;
	else if (arr[n]) return arr[n];
	else return arr[n] = (solution(n - 1) + solution(n - 2)) % 15746;
}
int main(void)
{
	int N;
	cin >> N;
	cout << solution(N);
	return 0;
}

(실행)

2. 풀이

1과 00, 11로 2진 수열을 만들고 길이가 N만큼일 때 만약 N에 0을 넣는다면 0이 나오고, N에 1을 넣으면 (1)로 1이 나오고, N에 2를 넣으면 (00, 11)로 2가 나온다. 그리고 N에 3을 넣으면 (001, 100, 111)로 3이 나온다. 그리고 4를 넣으면 (0000, 0011, 1100, 1111, 1001)로 5가 나온다. 그렇다면 N을 기준으로 각각 도출된 값들을 오름차순으로 나열해보면 (0, 1, 2, 3, 5)가 나오는데 뭔가 익숙하다.

그렇다면 이걸 식으로 만들어보면 solution(N) = solution(N - 1) + solution(N - 2)라는 값이 나온다. 그렇다면 이것은 그저 피보나치 수열이기 때문에 피보나치 수열을 구하는 식을 만들면 된다. 그런데 N이 2일 경우 원래 피보나치 수열대로라면 2가 아닌 1이 나와야 하기 때문에 피보나치 수열을 저장하는 배열에 인덱스 값이 2일 경우 2를 미리 저장하게 한 뒤 동적 계획법으로 짜게 되면 빠르게 해결이 가능하다.

int arr[1000001] = { 0, 1, 2 };

int main(void)
{
	int N;
	cin >> N;
	cout << solution(N);
	return 0;
}

코드로 설명을 해보자면 먼저 함수에서 계산되는 결과를 저장하는 용도로 arr배열을 전역 변수로 선언을 한 뒤 0, 1, 2를 미리 초기화시켜준다. 사용자에게 N의 값을 입력받고 solution 함수를 실행하는데 N을 전달받는다.

int solution(int n)
{
	if (n == 0) return 0;
	else if (n == 1)return 1;
	else if (arr[n]) return arr[n];
	else return arr[n] = (solution(n - 1) + solution(n - 2)) % 15746;
}

그리고 n이 0일 때는 0을 반환하고 1일 때는 1을 반환한다. 그리고 arr [n]에 저장된 값이 있다면 arr [n]의 값을 반환하는데 그렇지 않다면 arr [n]에 solution(n - 1) + solution(n - 2)의 값으로 하는데 이 값에 % 15746을 해주는데 출력에 대한 설명을 보면 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다고 되어있기에 이렇게 해준다.

만약 여기서 15746을 나누지 않고 출력 시에 15746을 나누게 되면 "틀렸습니다."가 나올 텐데 아마도 오버플로우가 발생해서 그런 게 아닌가 싶다.

3. 느낀 점

해결방안이 보이지 않을 때 입력과 출력의 관계를 보는 게 상당히 도움이 되었다. 만약 문제 자체를 해결할 방법이 생각 안 난다면 입력과 출력된 결과의 관계를 살펴봐야겠다.