[백준 2661번] 좋은수열

문제 링크: https://www.acmicpc.net/problem/2661

2661번: 좋은수열

<문제 풀이> 백트래킹

DFS로 수열에 숫자를 하나씩 추가해 나가면 되는데, 숫자를 추가했을 때 좋은 수열이 되는 경우만 추가해야 된다.

121을 예를 들어보면

 

121에서 숫자 1을 추가하면 1211이 된다. 나쁜 수열이 되었으니 숫자를 추가할 수 없다.

121에서 숫자 2를 추가하면 1212가 된다. 나쁜 수열이 되었으니 숫자를 추가할 수 없다. 

121에서 숫자 3을 추가하면 1213이 된다. 좋은 수열이 되었으니 숫자를 추가할 수 있다.

 

[좋은 수열인지 판별하는 방법]

수열의 길이를 n이라고 하면 다음과 같이 비교할 수 있다

1자리로 이루어진 부분 수열 비교

2자리로 이루어진 부분 수열 비교

.

.

 

n/2자리로 이루어진 부분 수열 비교

 

->부분 수열이 모두 다르면 좋은 수열이다.

 

ex) 수열이 123123일 때

1자리로 이루어진 부분 수열 비교

1, 2, 3, 1, 2, 3

2자리로 이루어진 부분 수열 비교

12, 31, 23

6/2 == 3자리로 이루어진 부분 수열 비교

123, 123

 

이제 수열이 좋은 수열인지 판별하는 함수를 만들고 DFS를 진행하면 되는데, 숫자를 추가했을 때 좋은 수열인 경우만 숫자를 추가했으니깐 새로 추가한 숫자가 좋은 수열인지 판별할 때는 부분 수열 뒤에 2개만 확인하면 된다.

 

1자리 일 때

1, 2, 3, 1, 2, 3

2자리 일 때

12, 31, 23

3자리 일 때

123, 123

 

<C++ 소스코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int n;
 
bool isGood(string s) {
    int len = s.length();
    for (int i = 1; i <= len / 2; i++) {
        string a = s.substr(len - i, i);
        string b = s.substr(len - i * 2, i);
        if (a == b) return false;
    }
    return true;
}
 
string dfs(int depth, string &cur) {
    if (depth == n) {
        return cur;
    }
    for (int i = 1; i <= 3; i++) {
        char c = i + '0';
        string next = cur + c;
        if (isGood(next)) {
           string res = dfs(depth + 1, next);
           if (!res.empty()) return res;
        }
    }
    return "";
}
 
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    string start = "1";
    cout << dfs(1, start);
    return 0;
}