백준 2661 - 좋은 수열 (C++)

 

N의 길이를 가지는 좋은 수열 중, 하나의 수로 표현했을 때 가장 작은 수가 되는 좋은 수열을 구하자.

 

좋은 수열이란, 나쁜 수열이 아닌 수열이다.

나쁜 수열이란, 특정 부분 수열이 반복되는 부분 수열이 존재하는 수열이다.

 

예를 들어, 123123 은 123이라는 부분 수열이 반복되는 123123이라는 부분 수열이 존재한다.

312123 은, 12라는 부분 수열이 반복되는 1212라는 부분 수열이 존재한다.

11은, 1이라는 부분 수열이 반복되는 11이라는 부분 수열이 존재한다.

 

문제 풀이

이 문제는 특별한 규칙을 찾을 수는 없었다. 하나하나 경우의 수를 탐색하는 방법말고는 다른 방법은 딱히 없는 듯 하다.

본인은 백트래킹을 활용하여 문제를 해결하였다.

 

문자열의 맨 뒤에 1, 2, 3을 더한 뒤, 해당 수열이 좋은 수열인지 탐색하는 것이다.

 

그렇다면, 해당 수열이 나쁜 수열인지 좋은 수열인지 판단하는 방법이 필요하다.

본인은 맨 뒤에서부터 수열의 절반만큼 탐색하며 판단하였다.

 

예를 들어 "12323" 을 판별한다고 해보자.

 

맨 뒤에서 1글자를 기준으로 비교하게 되면, "12323" 이렇게 파란색 문자열과 빨간색 문자열을 비교하게 된다.

두 문자열이 같다면, 나쁜 수열인 것이다.

 

한 글자를 비교했을 때, 좋은 수열이었다면 이번엔 두 글자를 비교해보는 것이다. "12323" 이렇게 말이다.

이번엔, 파란색 문자열과 빨간색 문자열이 동일하므로, 나쁜 수열임을 판단할 수 있다.

 

하지만 끝을 기준으로 비교하게 되면 "132321" 이렇게 중간에 수열이 반복되는 경우는 탐지할 수가 없을 것 처럼 보인다. 하지만, 아니다. 왜냐하면, 재귀함수를 통해 1글자씩 더해가며 판별을 반복할 것이기 때문이다. 

 

맨 처음엔, 빈 문자열에 1을 더한다.

문자열 : "1"

 

위의 문자열을 판별한다.

좋은 수열인 경우, 문자열의 뒤에 "1"을 더한다

문자열 : "11"

 

또 위의 문자열을 판별한다.

좋은 수열인 경우, 문자열의 뒤에 "1"을 더한다.

하지만, 현재 문자열은 나쁜 수열이다.그러므로, 뒤의 1을 뺀 뒤, 2를 더한다. (만약 맨 뒤가 2인 상태에서 나쁜 수열로 판단된다면, 2를 빼고 3을 더한다. )

문자열 : "12"

 

위의 문자열을 판별한다.좋은 수열인 경우, 문자열의 뒤에 "1"을 더한다.

문자열 : "121"

 

이 과정을 의사 코드로 작성하면, 아래와 같다.

void Recursive(std::string _Str, int _MaxLength)
{
	if (_Str이 나쁜 수열이면?)
	{
            return;
	}

	if (길이가 MaxLength까지 왔는데, 나쁜 수열이 아니다?)
	{
            정답 발견!
            return;
	}
    
	Recursive(_Str + "1", _MaxLength);
	Recursive(_Str + "2", _MaxLength);
	Recursive(_Str + "3", _MaxLength);
}

 

이렇게 재귀함수를 활용하여, 문자열의 길이를 1씩 증가시키며 좋은 수열을 찾는 것이다.

그러므로, 중간에 반복되는 수열이 있는 경우는 있을 수가 없다.

 

(중간에 있는 반복되는 수열은 현재 문자열보다 길이가 짧은 문자열에서는 가장 뒤에 있는 반복되는 수열일 수 있다. 거기서 반복되는 수열이 발견되면서 return 해버리기 때문에, 중간에서 발견되는 반복되는 수열은 있을 수 없다.)

 

또한, 재귀함수를 보면, 1을 우선적으로 더하고 그 이후 2를 더하고 마지막에 3을 더하고 있다.즉, 가장 먼저 발견되는 좋은 수열이 정답이 될 수 밖에 없다.

 

1-> 11 -> 12 -> 121->  1211 -> 1212 -> 1213 ... 이런 식으로 숫자 크기대로 탐색하기 때문이다.

 

풀이 코드

int Length = 0;
std::cin >> Length;

먼저, 수열의 길이를 입력받는다.

 

Recursive("", Length);

std::cout << Answer;

return 0;

이후, 재귀함수를 실행한 뒤에 답을 출력할 것이다.

 

void Recursive(std::string _Str, int _MaxLength)
{
    if (Answer != "")
    {
        return;
    }

    if (Check(_Str) == false)
    {
        return;
    }

    if (_Str.size() >= _MaxLength)
    {
        Answer = _Str;
        return;
    }
    
    Recursive(_Str + "1", _MaxLength);
    Recursive(_Str + "2", _MaxLength);
    Recursive(_Str + "3", _MaxLength);
}

Answer이 ""이 아니라면, 이미 답을 구했다는 의미이므로 모든 재귀함수를 종료시킨다.

 

Check는 해당 수열이 좋은 수열인지 판단하는 함수이다. 나쁜 수열이라면 return해주었다.

 

길이가 MaxLength될 때 까지 나쁜 수열로 판별되지 않은 수열이 있다면 정답으로 저장해주었다.

 

문자열의 맨 뒤에 1을 붙이는 경우를 우선적으로 재귀적 탐색한 뒤, 정답을 발견하지 못하면 2를 붙이며 탐색하고, 그 때도 발견하지 못하면 3을 붙여 순차적으로 탐색하도록 하였다.

 

bool Check(const std::string& _Str)
{
    int Size = _Str.size();

    for (int i = 1; i <= Size / 2; i++)
    {
        int Start = Size - i * 2;
        
        if (_Str.substr(Start, i) == _Str.substr(Start + i, i))
        {
            return false;
        }
    }

    return true;
}

Check함수의 내부 코드이다.

문자열의 끌을 기준으로, 1자리, 2자리 3자리.... (문자열의 길이 / 2)자리의 수열이 앞에서 반복되고 있는 지를 판별하였다.

 

12131213

12131213

12131213

12131213

 

위와 같은 순서로, 파란색 문자열과 빨간색 문자열을 비교한 것이다.

위에서도 말했지만, 중간에서 반복되는 부분 수열은, 해당 수열이 끝에 있을 때 이미 걸러지기 때문에 중간에서는 반복되는 수열이 발견될 수 없다.

 

(123231 에서, 23과 23이 반복되고 있지만,이는 12323 에서 이미 걸러지고 return 되므로 123231이라는 문자열은 탐색되지 않는다.)

 

 

코드 전문

#include <iostream>
#include <vector>
#include <set>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

std::string Answer = "";

bool Check(const std::string& _Str)
{
    int Size = _Str.size();

    for (int i = 1; i <= Size / 2; i++)
    {
        int Start = Size - i * 2;
        
        if (_Str.substr(Start, i) == _Str.substr(Start + i, i))
        {
            return false;
        }
    }

    return true;
}

void Recursive(std::string _Str, int _MaxLength)
{
    if (Answer != "")
    {
        return;
    }

    if (Check(_Str) == false)
    {
        return;
    }

    if (_Str.size() >= _MaxLength)
    {
        Answer = _Str;
        return;
    }
    
    Recursive(_Str + "1", _MaxLength);
    Recursive(_Str + "2", _MaxLength);
    Recursive(_Str + "3", _MaxLength);
}

int main()
{
    Init();

    int Length = 0;
    std::cin >> Length;

    Recursive("", Length);

    std::cout << Answer;

    return 0;
}