[BOJ] 2661: 좋은 수열

문제 링크

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

2661번: 좋은수열

풀이

예전에 누군가의 코드를 따라치면서 대충 이해만 하고 넘어갔던 문제다. 이번에 다시 백트래킹을 풀어보면서

제대로 풀어보기로 했다. 백트래킹으로 string에 숫자를 하나씩 붙여나가는 방식으로 코드를 작성했다.

처음에 depth 1인 str은 '1'로 시작하는 백트래킹 함수를 호출했다. 그 이유는 좋은 수열중 가장 작은 수 이므로

맨 앞자리는 1일 것이다. 매 함수마다 지금까지 만들어진 수열이 좋은 수열인지 판별하고 아니라면 retrun 하는

방식으로 시간을 조금이라고 줄이려했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int N;
vector<char> alpha;
 
void backtracking(int depth, string str) {
    for (int i = 1; i <= str.length() / 2; i++) {
        for (int j = 0; j < str.length() / i - 1; j++) {
            if (str.substr(j, i) == str.substr(j + i, i))
                return;
        }
    }
    if (depth == N) {
        cout << str << "\n";
        exit(0);
    }
    if (str[str.length() - 1] == '1') {
        backtracking(depth + 1, str + '2');
        backtracking(depth + 1, str + '3');
    }
    else if (str[str.length() - 1] == '2') {
        backtracking(depth + 1, str + '1');
        backtracking(depth + 1, str + '3');
    }
    else if (str[str.length() - 1] == '3') {
        backtracking(depth + 1, str + '1');
        backtracking(depth + 1, str + '2');
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
 
    string temp = "";
    backtracking(1, temp + '1');
    return 0;
}
 
 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int N;
vector<char> alpha;
 
void backtracking(int depth, string str) {
    for (int i = 1; i <= str.length() / 2; i++) {
        if (str.substr(str.length() - i, i) == str.substr(str.length() - i * 2, i))
            return;
    }
    if (depth == N) {
        cout << str << "\n";
        exit(0);
    }
    if (str[str.length() - 1] == '1') {
        backtracking(depth + 1, str + '2');
        backtracking(depth + 1, str + '3');
    }
    else if (str[str.length() - 1] == '2') {
        backtracking(depth + 1, str + '1');
        backtracking(depth + 1, str + '3');
    }
    else if (str[str.length() - 1] == '3') {
        backtracking(depth + 1, str + '1');
        backtracking(depth + 1, str + '2');
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
 
    string temp = "";
    backtracking(1, temp + '1');
    return 0;
}
 
 

맨 뒤에 있는 숫자가 포함되게 길이 1만큼 2만큼 ... string의 길이 / 2만큼 만 비교하고 좋은 수열이 아니면 return 하면 된다. 만약 123123이라면 맨 뒤에있는 2와3, 그리고 31과 23 그리고 123과 123만 비교하면 된다. 이미 그 앞에는 그 전에 다 판별을 했기 때문에 또 하면 중복인 것이다. 121231인 str은 만들어 질 수 없다. 왜냐 그 전에 이미 1212가 됐을 때 return 됐을 것이다. 이렇게 하면 시간복잡도를 줄일 수 있다.