[2661번] 좋은수열

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 백트래킹(Backtraking)

이 문제를 통해 백트래킹 알고리즘이 어떻게 동작하는지 알아보자

    for (int i = 1; i <= 3; i++)

    {

        str.push_back(i+'0');

 

        if (backTraking(here + 1) == 0)

            return 0;

 

        str.pop_back();

    }

백트래킹이 돌아가는 기본 구조이다.

원하는 값을 넣어보고 그 값이 만족하지 않는다면 다시 빼내는 과정이다.

현재 1,2,3으로만 좋은 수열을 구해야 된다.

112는 좋은 수열이 아니다.

112에서 11이 인접해서 나오기 때문이다.

1212도 좋은 수열이 아니다.

1212의 12가 인접해서 나오기 때문이다.

따라서 이러한 인접하지 않으면서 가장 작은 좋은 수열을 구하기 위해서는

위의 for문에서 이용하듯이 1, 2, 3을 한번씩 넣어보고 좋은 수열인지 체크해주면 된다.

 

    for (int i = 1; i <= here / 2; i++)

        if (equal(str.c_str() + here - i, str.c_str() + here, str.c_str() + here - i * 2))

            return -1;

 

이 문제의 백트래킹 알고리즘핵심이다.

위의 코드가 동작하는 과정은 다음과 같다.

예를들어 13123123 이라는 수열이 있고 1을 넣었을 때

13231231 3과 1을 검사

13231231 12와 31을 검사(보라색 글자는 겹쳐진 글자)

13231231 231과 231을 검사

여기서 중복이 걸리기 때문에 return -1을 하게 될 것이다.

이렇게 되면

    for (int i = 1; i <= 3; i++)

    {

        str.push_back(i+'0');

 

        if (backTraking(here + 1) == 0)

            return 0;

 

        str.pop_back();

    }

위의 알고리즘에 의해 if(-1 == 0)이 될 것이고 해당하지 않으니

str.pop_back()를 통해 문자를 빼고 다음값인 2를 넣어 13231232로 검사하는 방식이 이루어 질 것이다.

이렇게 계속 진행하다가 

    if (here == n)

    {

        for (int i = 0; i < n; i++)

            printf("%c", str[i]);

 

        return 0;

    }

here == n 즉, 모든 값이 정해진 경우 return 0;을 하여 backtraking 함수의 모든 return을 0으로 돌려 탈출시키고 끝을 낸다.

소스 코드 :(소스 코드 2개중 2번째 코드는 가독성이 좀 더 높은 코드로 다시 갱신하였습니다.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include <iostream> #include <cstdio> #include <string>   using namespace std;   int n; string str;   int backTraking(int here) {     int len = str.size();       for (int i = 1; i <= here / 2; i++)         if (equal(str.c_str() + here - i, str.c_str() + here, str.c_str() + here - i * 2))             return -1;       if (here == n)     {         for (int i = 0; i < n; i++)             printf("%c", str[i]);           return 0;     }              for (int i = 1; i <= 3; i++)     {         str.push_back(i+'0');           if (backTraking(here + 1) == 0)             return 0;           str.pop_back();     } }   int main() {     scanf("%d", &n);       backTraking(0);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
int n;
string str;
 
int backTraking(int here)
{
    int len = str.size();
 
    for (int i = 1; i <= here / 2; i++)
        if (equal(str.end() - i, str.end(), str.end() - i * 2)) // << 이렇게 푸는 것이 좀 더 가독성이 높다.
            return -1;
 
    if (here == n)
    {
        for (int i = 0; i < n; i++)
            printf("%c", str[i]);
 
        return 0;
    }
 
    for (int i = 1; i <= 3; i++)
    {
        str.push_back(i + '0');
        
        if (backTraking(here + 1) == 0)
            return 0;
 
        str.pop_back();
    }
}
 
int main()
{
    scanf("%d", &n);
 
    backTraking(0);
 
    return 0;
}
 
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>