좋은수열 / 백준 (Baekjoon) / 2661

---

좋은수열 / 백준 (Baekjoon) / 2661

** 여기서 다루는 알고리즘 문제는 저의 창작 문제가 아닐 경우, 저작권 관련 문제를 방지하고자, 문제의 대략적인 설명 및 요구사항만 소개하고 있습니다. 

** 이 공간에서 공유되는 풀이 및 Source code는 제 개인의 학습 목적이며, 당연히 최선의 정답이 아닙니다. 

** 혹시 더 나은 방법이나 아이디어가 있으신 경우에는, 댓글에 의견을 공유해주시면 감사하겠습니다.

** Source code는 C 언어로 작성되었습니다.

---

알고리즘 분류 및 개요

     - Backtracking (백트래킹)

 

 

Input / output

• 입력

 입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

• 출력

 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

 

주의 사항

• 전형적인 backtracking 풀이법으로 풀이가 가능하나, n queen문제와는 다르게, solution이 단 하나만 존재하므로, 가장 작은 수 하나만 출력하면 이후에 더이상 추가 알고리즘이 동작할 필요가 없습니다. (complete_flag가 활용되어야 함)
• 나쁜 수열 check만 적절히 해준다면 큰 어려움 없이 해결이 가능합니다.

Source code

---

///////////////////////////////////////////////
// - Backjoon 2661 : 좋은 수열
// - https://www.acmicpc.net/problem/2661
///////////////////////////////////////////////

#include <stdio.h>

int max_length;

typedef unsigned int	(u32);
typedef unsigned short  (u16);
typedef unsigned char	(u8);

typedef signed int		(s32);
typedef signed short	(s16);
typedef signed char		(s8);

#define MAX_TEST_NUM	(80)

u8 input_buf[MAX_TEST_NUM];

u8 complete_flag = 0;

static u8 __inline IsComplete( u8 depth )
{
	if (depth == (max_length - 1))
	{
		return 1;
	}

	return 0;
}

static void FinalProcess( u8 *arr )
{
	int i;

	for (i = 0; i < max_length; i++)
	{
		printf("%d", arr[i]);
	}
	printf("\n");
}

static u8	IsValidCandidate(u8 *arr, u8 depth)
{
	int i, j;
	u8 result = 1;
	u8 range = (depth + 1) >> 1;

	for (i = 1; i < range; i++)
	{
		u8 bad_arr_check_flag = 1;
		
		for (j = 0; j <= i; j++)
		{
			if (arr[depth - j] != arr[depth - j - (i + 1)])
			{
				bad_arr_check_flag = 0;
				break;
			}
		}

		if (bad_arr_check_flag == 1)	
			return 0;
	}

	return 1;
}

static void FindNextTargets(u8 *arr, u8 depth, u8 *next_targets, u8 *num_of_next_targets)
{
	int i;
	u8 num_of_valid_canditate = 0;

	for (i = 1; i <= 3; i++)
	{
		if (arr[depth - 1] == i)
			continue;
		else
		{
			arr[depth] = i;

			if (IsValidCandidate(arr, depth))
			{
				next_targets[num_of_valid_canditate++] = i;
			}

			arr[depth] = 0;
		}
	}

	*num_of_next_targets = num_of_valid_canditate;
}

u8 Backtracking( u8 *arr, u8 depth )
{
	int i;

	// Check whether this combination is the solution or not.
	if (IsComplete( depth ))
	{
		FinalProcess( arr );
		complete_flag = 1;	// Finish.
	}
	else
	{
		u8 num_of_next_targets = 0;
		u8 next_targets[2];

		// Increase the count of depth.
		depth++;

		// Update the list of next targets and the number.
		FindNextTargets(arr, depth, next_targets, &num_of_next_targets);

		// Check every feasible target.
		for (i = 0; i < num_of_next_targets; i++)
		{
			arr[depth] = next_targets[i];
			Backtracking(arr, depth);

			// If finished, every function is return '0' and closed.
			if (complete_flag)	return 0;
		}
	}
}

int main(void)
{
	int i;

	scanf("%d", &max_length);

	for (i = 1; i < 3; i++)
	{
		if (complete_flag == 0)
		{
			input_buf[0] = i;
			Backtracking(input_buf, 0);
		}
	}

	return 0;
}

---

난이도 / 중요도 / 재시도

  ★★☆☆☆ / ★★☆☆☆ / x 0

출처 / 관련 링크

- Baekjoon online judge : https://www.acmicpc.net/problem/2661

- Backtracking 알고리즘 소개 : http://jayce-with.tistory.com/16

Test input file

-