[C/C++] 백준 #2661 좋은수열(백트래킹)

이번 문제는 백트래킹을 이용해서 문제를 풀었습니다.

현재 위치가 올바른지 아닌지를 검사하는데, 조금 더 우수한 알고리즘을 이용했다면, 더 좋게 할 수 있겠지만, 저는 단순한 알고리즘을 이용했습니다.  더 좋은 알고리즘을 찾기 위해서 노력을 안 한 것도 있었겠지만, 글을 쓰는 시점에서 생각해도 좋은 알고리즘을 찾는 것이 쉽지는 않습니다.

 

good sequence problem

 

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

#### 1. `solve` 함수
이 함수는 재귀적으로 좋은 수열을 생성하는 역할을 합니다. 함수의 매개변수는 다음과 같습니다:
- `v[]`: 현재까지 생성된 수열을 저장하는 배열
- `c`: 현재까지 생성된 수열의 길이
- `n`: 생성하고자 하는 수열의 길이

bool solve(int v[], int c, int n)
{
    if(c == n) return true;
    int j, k;
    for(int i = 1; i <= 3; i++)
    {
        for(j = c-1; j >= c/2; j--)
        {
            if(i != v[j]) continue;
            for(k = 1; k < c-j; k++)
                if(v[c-k] != v[j-k]) break;
            if(k == c-j) break;
        }
        if(j >= c/2) continue;
        v[c] = i;
        if(solve(v, c+1, n)) return true;
    }
    return false;
}

- `if(c == n) return true;`: 현재까지 생성된 수열의 길이가 n이면, 좋은 수열을 찾았으므로 true를 반환하여 재귀를 종료합니다.
- `for(int i = 1; i <= 3; i++)`: 수열의 다음 값으로 1, 2, 3 중 하나를 시도합니다.
- `for(j = c-1; j >= c/2; j--)`: 수열의 중복을 피하기 위해 현재 위치에서 시작하여 반까지 탐색합니다.
- `if(i != v[j]) continue;`: 시도 중인 값이 현재 수열의 값과 다르면 다음 값으로 넘어갑니다.
- `for(k = 1; k < c-j; k++) if(v[c-k] != v[j-k]) break;`: 현재 값과 시도 중인 값이 동일하면, 중복된 부분 수열이 있는지 확인합니다.
- `if(k == c-j) break;`: 중복된 부분 수열이 발견되면 반복을 중단합니다.
- `if(j >= c/2) continue;`: 중복된 부분 수열이 있으면 다음 값을 시도합니다.
- `v[c] = i;`: 중복된 부분 수열이 없으면 수열에 값을 추가합니다.
- `if(solve(v, c+1, n)) return true;`: 재귀적으로 다음 값을 탐색합니다.
- `return false;`: 가능한 모든 값을 탐색한 후에도 좋은 수열을 찾지 못하면 false를 반환합니다.

#### 2. `main` 함수
`main` 함수는 프로그램의 시작점으로, 사용자로부터 수열의 길이 n을 입력받고 좋은 수열을 생성하여 출력합니다.

 

int main()
{
    int n, v[80], s, k;
    scanf("%d", &n);
    v[0] = 1;
    solve(v, 1, n);
    for(int i = 0; i < n; i++) printf("%d", v[i]);
    putchar('\n');
}

- `scanf("%d", &n);`: 사용자로부터 수열의 길이 n을 입력받습니다.
- `v[0] = 1;`: 수열의 첫 번째 값을 1로 초기화합니다.
- `solve(v, 1, n);`: 재귀 함수 `solve`를 호출하여 좋은 수열을 생성합니다.
- `for(int i = 0; i < n; i++) printf("%d", v[i]);`: 생성된 좋은 수열을 출력합니다.
- `putchar('\n');`: 출력 후 개행 문자를 추가합니다.

이 프로그램은 좋은 수열을 찾기 위해 재귀와 백트래킹을 활용하여 모든 가능한 수열을 탐색합니다. 중복된 부분 수열을 확인하며, 조건을 만족하는 첫 번째 수열을 찾으면 이를 출력하고 종료합니다.

 

전체 소스입니다.

//------------------------------------------------
//    baekjoon #2661
//        - by Aubrey Choi
//        - created at 2019-07-22
//------------------------------------------------
#include <stdio.h>

bool solve(int v[], int c, int n)
{
    if(c == n) return true;
    int j, k;
    for(int i = 1; i <= 3; i++)
    {
        for(j = c-1; j >= c/2; j--)
        {
            if(i != v[j]) continue;
            for(k = 1; k < c-j; k++)
                if(v[c-k] != v[j-k]) break;
            if(k == c-j) break;
        }
        if(j >= c/2) continue;
        v[c] = i;
        if(solve(v, c+1, n)) return true;
    }
    return false;
}

int main()
{
    int n, v[80], s, k;
    scanf("%d", &n);
    v[0] = 1;
    solve(v, 1, n);
    for(int i = 0; i < n; i++) printf("%d", v[i]);
    putchar('\n');
}