BaekJoon 2661 좋은수열

Link https://www.acmicpc.net/problem/2661

소스결과 1988 KB / 0 ms

출처 Baekjoon, KOI 1997

언어 C++ 17

분류 수학, 백트래킹

 

설명

1, 2, 3으로 이루어진 수열 중 인접한 두개의 부분 수열이 동일한 하지 않은 최솟값 수열을 출력하는 문제이다.

 

첫 자리를 제외하고 나머지 자리는 2번씩 검색해야하는 느낌이 드는 문제이다. 시간 제한이 1초인 점이 의심스럽다.

하지만 위 문제는 간단히 생각하면 앞자리가 1인 경우가 항상 최소가 되는 수열이다.

수열을 검사하는 부분을 최대한 간략화 시키기만 한다면 쉽게 문제가 풀린다.

 

알고리즘

1. 수를 입력받는다.

2. 현재 위치의 문자 값을 1 ~ 3 사이로 설정한다.

 2 - 1. 0번 인덱스를 제외한 나머지 부분에서 문자를 설정하는 경우 현재까지 입력된 문자열에 대해서 좋은수열인지 판별한다.

 2 - 2. 현재 문자를 넣은 후 좋은 수열이라고 판별이 되면 다음 위치로 이동후 2번 함수를 반복한다.

 2 - 3. 목표 위치에 도달하는 경우 모든 함수를 종료시킨다.

3. 문자열을 출력후 종료한다.

 

좋은 수열 판별 함수.

1. 검사할 문자열 길이를 1 부터 문자열 길이의 절반까지 반복한다.

 1 - 1. 문자열 길이만큼 대칭 구조로 검사한다. 중복이 되지 않는 경우를 발견시 반복을 종료 후 검사할 문자열 길이를 1 늘이는 것을 반복한다.

 1 - 2. 수열이 반복되는 경우가 발견되면 false를 반환한다.

 

소스코드

#include <iostream>

using namespace std;

const short MAX = 80;
char number[MAX + 1] = {};
int n;

bool isAble(int pos)
{
	for (int i = 1; i <= (pos + 1) / 2; i++)
	{
		bool duple = false;
		for (int j = 0; j < i; j++)
		{
			if (number[pos - j] != number[pos - i - j]) {
				duple = duple | true;
				break;
			}
		}

		if (!duple)
			return false;
	}
	return true;
}

int solution(int pos)
{
	if (pos == n)
	{
		return 0;
	}
	else
	{
		for (int i = '1'; i < '1' + 3; i++)
		{
			number[pos] = i;
			if (isAble(pos))
			{
				int res = solution(pos + 1);
				if (res != -1)
					return res;
			}
		}
	}

	return -1;
}

int main()
{
	cin >> n;

	solution(0);
	
	cout << number;

	return 0;
}