[G5] 백준 15918번 랭퍼든 수열쟁이야!! C++ 백트래킹

리뷰

 

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

좀 더 예쁘게 풀 수 있었을 것 같은데 풀다보니 너무 지저분해졌다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 자연수의 개수를 저장할 변수
• x, y : 이미 주어진 같은 수여야 하는 두 인덱스를 저장할 변수
• uc : 사용한 자연수의 개수를 저장할 변수
• ans : 완성된 랭퍼드 수열의 개수를 저장할 변수
• used : 이미 사용한 자연수를 체크하기 위한 배열
• arr : 랭퍼드 수열 정보를 저장할 배열

 

함수

1. bt

void bt( int level )
{
	if ( level > 2 * n )
		return;

	for ( int i = 1; i <= n; ++i )
	{
		if ( used[ i ] )
			continue;

		if ( level + i + 1 > 2 * n )
			continue;

		if ( arr[ level + i + 1 ] )
			continue;

		used[ i ] = true;
		arr[ level ] = i;
		arr[ level + i + 1 ] = i;
		++uc;
		if ( uc != n )
		{
			for ( int j = level + 1; j <= 2 * n; ++j )
			{
				if ( !arr[ j ] )
				{
					bt( j );
					break;
				}
			}
		}
		else ++ans;
		--uc;
		arr[ level + i + 1 ] = 0;
		arr[ level ] = 0;
		used[ i ] = false;
	}
}

 

백트래킹을 통해 랭퍼드 수열을 만들 수 있는 경우를 체크하고, 개수를 세기 위한 함수

 

 

문제풀이

1. n, x, y값을 입력 받는다.
2. 변수 diff를 y-x-1로 초기화한다.
3. used배열의 diff를 true로 변경한다.
4. arr[x], arr[y]를 diff로 초기화한다.
5. uc를 1만큼 증가시킨다.
6. bt함수에 통해 x가 1인 경우 2를, 아닌 경우 1을 매개변수로 전달하여 호출한다.
7. bt함수에서 level을 매개변수로 전달받는다.
8. 기저 조건으로 level이 2n을 초과한 경우 즉시 반환한다.
9. 1~n을 순회하며 이미 사용했거나, 오른쪽 인덱스가 2n을 초과했거나, 이미 오른쪽인덱스에 다른 수가 있을 경우 continue처리한다.
10. 위에 해당하지 않는 경우 used배열에 현재 자연수를 true로 변경해준다.
11. arr[level]과 arr[level+i+1]을 현재 자연수로 마킹해준다.
12. uc를 증가시키고, 만약 uc가 n에 도달하지 않은 경우 다음 비어있는 인덱스를 찾아 재귀를 호출한다.
13. uc가 n에 도달한 경우 ans를 증가시키고, uc, arr, used를 원상복구 시킨다.
14. 백트래킹을 완료 하고, ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 주어진 x, y를 통해 특정 인덱스를 특정 자연수로 고정시키는 방법을 사용해주었다.
2. 원래는 재귀 단계인 level로만 백트래킹을 수행하려고 했지만, 순차 처리에 어려움을 느껴 빈 공간을 찾아 재귀를 수행하는 방향으로 로직을 작성하였다. 시간 복잡도는 그렇게 만족스럽지는 못한듯 하다.

 

정답 코드

#include <iostream>
using namespace std;

const int N = 13;
int n, x, y, uc, ans;
bool used[ N ];
int arr[ N * 2 ];

void bt( int level )
{
	if ( level > 2 * n )
		return;

	for ( int i = 1; i <= n; ++i )
	{
		if ( used[ i ] )
			continue;

		if ( level + i + 1 > 2 * n )
			continue;

		if ( arr[ level + i + 1 ] )
			continue;

		used[ i ] = true;
		arr[ level ] = i;
		arr[ level + i + 1 ] = i;
		++uc;
		if ( uc != n )
		{
			for ( int j = level + 1; j <= 2 * n; ++j )
			{
				if ( !arr[ j ] )
				{
					bt( j );
					break;
				}
			}
		}
		else ++ans;
		--uc;
		arr[ level + i + 1 ] = 0;
		arr[ level ] = 0;
		used[ i ] = false;
	}
}

int main()
{
	cin >> n >> x >> y;

	int diff = y - x - 1;
	used[ diff ] = true;
	arr[ x ] = diff;
	arr[ y ] = diff;
	++uc;

	bt( x == 1 ? 2 : 1 );
	cout << ans;
}