[백준] 2661 좋은 수열

 

 

문제 설명을 보고 오자.

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

2661번: 좋은수열

 

이 문제는 백트래킹을 이용한 탐색 문제이다. 조건을 생각하는 구성이 복잡하지만, 역할을 잘 나누면 풀이가 한결 편해질 것이다.

 

인접한 두 개의 부분 수열이 동일한 것이 있으면, 해당 수열은 나쁜 수열로 다음 경우의 수로 넘어가야 한다. 그렇게 하기 위해서는 한 자리에 1~3이 들어가며, 조건에 맞으면 다음 과정을 탐색할 수 있는 백트래킹 기법으로 풀이하면 될 것이다.

 

탐색하는 함수를 생각해보자. 시작하는 인덱스가 N + 1 이 되면 종료하게 하자. 왜냐하면 탐색을 모두 완료했기 때문이다. 탐색을 종료하는 flag도 전역변수로 두어 종료조건을 만들어 보자. 그렇지 않으면 좋은 수열인지 체크하는 함수를 만들어 좋은 수열이면 수열길이 + 1 을 탐색한다. (다음 탐색으로 넘어간다)

 

좋은 수열을 검사하는 함수는, 브루트 포스를 이용해 모든 경우의 수를 검사한다. 최대 N개의 길이의 수열이면 N/2 길이의 수열만 검사하면 된다. 1부터 N/2까지의 길이를 검사하고, 처음부터 끝까지 따로 다 검사한다.

 

#include <iostream>
#include <algorithm>
 
int arr[81];
int N, end;
 
void print(int len)
{
    for (int i = 1; i < len; i++)
        printf("%d", arr[i]);
    printf("\n");
}
 
/* 탐색할 곳이 좋은 문자열인지 아닌지 */
int is_good(int start, int len)
{
    int i, ans = 0;
    for (i = start; i < start + len; i++)
    {
        if (arr[i] == arr[i + len])
            ans++;
    }
    if (ans == len)
        return (0);
    else
        return (1);
}
 
/* 좋은수열인지 아닌지 확인하는 함수 */
/* 1번 인덱스 부터 max 까지 */
int good_check(int max)
{
    /* 몇 줄짜리 검사 */
    for (int i = 1; i <= max / 2; i++)
    {
        /* 몇 번부터 검사 */
        for (int j = 1; j <= max - (i * 2) + 1; j++)
        {
            if(!is_good(j, i))
                return (0);
        }
    }
    return (1);
}
 
void cal(int index)
{
    int num = 1;
    if (end)
        return;
    if ((index == N + 1) && !end)
    {
        print(index);
        end = 1;
        return;
    }
    while (num <= 3)
    {
        arr[index] = num;
        if (good_check(index))
            cal(index + 1);
        num++;
    }
}
 
int main()
{
    scanf("%d", &N);
    end = 0;
    cal(1);
    return (0);
}

 

백트래킹 문제는 다른 문제에 비해서 비교적 난이도가 풀만한 것 같다.