[백트래킹] 좋은 수열 (백준 2661번)

 

여기에 작성된 코드는 절대로 좋은 코드가 아니니, 참고하지 말 것!

 

---

 

 

 

#include <iostream>
#include <vector>
using namespace std;
 
/*
 
1232123 이라는 숫자가 있다고 할 때,
기준점을 하나씩 옮겨가며, 양측의 숫자들이 동일한 부분수열인지 비교한다.
 
1 232123 : 0 1    /1과 2가 동일한 숫자가 아니다. // clear
12 32123 : 1 2    /2와 3이 동일한 숫자가 아니다. // clear
12 32123 : 0 2    /1과 3이 동일한 숫자가 아니고. // (더 볼 필요가 없다.) 2와 2는 동일한 숫자가 맞다.
123 2123 : 2 3    /3과 2가 동일한 숫자가 아니다. // (더 볼 필요가 없다.)
123 2123 : 1 3, 2 4     /2와 2가 동일한 숫자고, 3과 1은 동일한 숫자가 아니다.
123 2123 : 0 3,         /1과 2는 동일한 숫자가 아니고 // 2와 1은 동일한 숫자가 아니고, 3과 2는 동일한 숫자가 아니다.
 
1232 123 :
...
12321 23 :
...
123212 3 :
 
다시 설명하면, 한 기준점 i가 우측으로 이동하고 있을 때,
좌측에 남아 있는 숫자의 개수만큼 비교를 해야 하므로 j < 좌측 항의 개수만큼에 대하여
 
i- j + k와 i + k를 비교하되 비교를 해야 한다.
즉, 3개의 for문이 필요함을 알 수 있고, 이 중에 1개라도 true가 나오면 나쁜 수열이라 할 수 있다.
 
근데 정말 이렇게까지 해서 문제를 푸는지가 의문이다.
더 좋은 방법이 있을 거 같으나, 일단 내가 떠올린 방법은 이상이다.
 
*/
 
//bool check(int num[], int count) // num은 숫자가 저장된 배열이고, count는 숫자의 개수다.
bool check (vector<int> numbers) // 그냥 vector로 만드는 게 좋을 거 같다.
{
    for (int i = 1; i < numbers.size(); i++)
    {
        for (int j = 1; j <= i; j++)
        {
            bool trueOrNot = true; // 만약 아래 for문이 끝날 때까지 true가 유지되면 나쁜 수열
 
                for (int k = 0; k < j; k++)
                {
                    if (i - j + k >= 0)
                        if (i + k < numbers.size())
                        {
                            if (numbers[i - j + k] != numbers[i + k])
                            {
                                //                            cout << i - j + k << ' ' << i + k << endl;
                                //                            나쁜 수열인 경우를 모두 출력한다.
 
                                trueOrNot = false;
                                break;
                                // 비교 중에 다른 부분이 나오는 순간 나쁜 수열이 아님으로 판명나서 break;
 
                            }
 
                            //else
                            //    cout << i - j + k << ' ' << i + k << endl;
                            //  비교해보기 위해서 좋은 수열도 모두 출력하게 하였다. (나쁘거나 좋거나 둘 다 출력하게.)
                        }
                        else
                        {
                            trueOrNot = false;
                            break;
 
                        }
                }
 
 
            if (trueOrNot) // 나쁜 수열(trueOrNot이 여전히 true이면)이 맞다면 false값 return
                return false;
        }
    }
    return true;
}
 
int main(void)
{
    vector<int> numbers;
    numbers.push_back(3);
    numbers.push_back(2);
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(1);
    numbers.push_back(3);
    numbers.push_back(2);
    numbers.push_back(3);
//    1232123 : 0 반환 (좋은 수열)
//     32121323
    cout << check(numbers);
}

다음 코드를 작동시키면 다음과 같은 출력 값이 나온다.

 

0 1

1 2

0 2

2 3

1 3

2 4

1 (false)

 

이는 각 인덱스끼리 비교하는 순서이며, 최종적으로 1과 3, 2와 4가 같은 부분순열을 발견해 종료되었음을 의미한다.

 

int length;
vector<int> numbers;
 
void dfs(int current)
{
    if (current == length)
    {
        for (int i = 0; i < length; i++)
            cout << numbers[i];
        cout << endl;
        return;
    }
 
    for (int i = 1; i <= 3; i++)
    {
        numbers.push_back(i);
        dfs(current + 1);
        numbers.pop_back();
    }
}
 
int main(void)
{
    cin >> length;
 
    dfs(0);
}

위의 코드를 작동시킨 다음 length를 입력하면,

1, 2, 3만을 가지고 만들 수 있는 length 길이 만큼의 수열들이 출력된다. (중복은 없다.)

 

void dfs(int current)
{
    if (current == length)
        if (check(numbers))
        {
            for (int i = 0; i < length; i++)
                cout << numbers[i];
            cout << endl;
            return;
        }
        else
            return;
 
    for (int i = 1; i <= 3; i++)
    {
        numbers.push_back(i);
        dfs(current + 1);
        numbers.pop_back();
    }
}

위의 dfs는 미리 만들어 놓은 check 함수를 합쳐서 좋은 수열만을 골라내게 한 것이다.

문제에서 가장 작은 좋은 수열을 출력하라고 했기 때문에, 이 안에 조건문 하나를 더 추가할 생각이다.

 

int minV = 987654321;
 
int makeNum(vector <int> numbers)
{
    int sum = 0;
    for (int i = 0; i < numbers.size(); i++)
    {
        int temp = numbers[i];
        for (int j = 0; j + i < numbers.size() - 1; j++)
        {
            temp *= 10;
        }
        sum += temp;
    }
    return sum;
}
 
void dfs(int current)
{
    if (current == length)
        if (check(numbers))
        {
//            for (int i = 0; i < length; i++)
//                cout << numbers[i];
//            cout << endl;
 
//            cout << makeNum(numbers); // 숫자로 변환이 잘 되는지 확인해보았다.
            if (makeNum(numbers) < minV)
                minV = makeNum(numbers);
            return;
        }
        else
            return;
 
    for (int i = 1; i <= 3; i++)
    {
        numbers.push_back(i);
        dfs(current + 1);
        numbers.pop_back();
    }
}

 

추가해봤다, 정상적으로 작동하는 것도 확인했다.

 

int main(void)
{
    cin >> length;
 
//    dfs(0);
    numbers.push_back(1);
    dfs(1); // 어차피 첫번째 수는 1이 들어갈 수밖에 없으니 1부터 시작하게 했다.
 
    cout << minV;
}

다만, 이 코드들을 모두 이어 붙일 경우 겨우 9%에서 시간초과가 발생한다.

이어서 하겠다.

 

---

나는 쉬는 동안 아래와 같은 생각을 하였다.

 

// 속도를 단축할 방법을 생각해봤는데,
// (최초로 조건이 만족할 때가 무조건 가장 작은 수다, 앞에서부터 추가해나가니까.)

// 일단 dfs의 for문에 check를 넣어서, 검사하게 했다, 이미 탈락한 후보에 대해서는
// 더 이상 뒤에 숫자를 붙여서 재검사하는 일이 없도록 끊어버렸다.
// 백트래킹의 의미에 더 맞게 바꾸었다.

// 그리고 check에 매개변수를 하나 추가해서, 이전에 검사한 부분에 대해 또 검사하는 일을 막고자 한다.
// 만약 123이 통과했던 수라면 123에 1을 붙여 1231을 만들었다면 123 , 1부터 검사하면 되지,
// 1 , 231로 나누어서 처음부터 재검사하게 할 이유가 없다.
// 이 두 가지를 사용하면 시간을 획기적으로 단축할 수 있을 거로 보인다.

 

하지만, 이런 방법을 동원한다고 해도 해결할 수 있을 거란 생각이 크지가 않다.

일단 check() 함수 자체가 3중 for문으로 되어 있기 때문에 연산 속도가 느릴 거란 생각이 들었다.

 

그리고 현재 백준 서버가 너무 느려져서, 문제를 하나 채점하는 데에도 거의 10분 가량이 걸리는데,

이런 방법으로 하다가는 오늘 안에 이 문제의 해결을 볼 수 있을지 걱정이 들었다.

그래서 아예 갈아 엎고, 매개변수들을 더 잘 활용해보는 게 어떤가 싶었다.

위의 코드는, 누군가에게는 간단한 문제를 너무 돌아가는 거 같아 수치스럽기 까지 하지만,

그럼에도 남겨놓고, 새로운 방식으로 풀어보겠다.

 

---