BOJ 2661번 좋은수열

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

github : https://github.com/junho0956/Algorithm/blob/master/2661/2661/%EC%86%8C%EC%8A%A4.cpp

 

코드에 대한 설명은 주석처리해놓았습니다.

현재 스트링으로 좋은수열인지 확인하기 위한 2개의 스트링을 만들어서

좋은수열의 조건을 만족한다면 dfs 진입해주면 됩니다.

 

#include <iostream>
#include <string>
using namespace std;
 
int N;
bool ans = false;
char arr[4] = { '0','1','2','3' };
 
// 좋은수열인지 확인
// 길이는 1부터 2배씩 늘어나고 그 길이가 스트링의 길이를 만족할때 까지만 탐색한다.
// 2개의 스트링을 만들어서 비교시 나쁜수열이라면 false 를 반환
bool check(string str, int idx) {
    string str1, str2;
    for (int i = str.size() - idx; i < str.size(); i++)
        str1 += str[i];
    for (int i = str.size() - (idx * 2); i < str.size() - idx; i++)
        str2 += str[i];
 
    if (str1.compare(str2) == 0) return false;
 
    return true;
}
 
void dfs(string str) {
    if (ans) return;
    if (str.size() == N) {
        cout << str;
        ans = true;
        return;
    }
 
    for (int i = 1; i <= 3; i++) {
        bool temp = true;
        for (int k = 1; k * 2 <= str.size() + 1; k++) {
            if (!check(str + arr[i], k)) {
                temp = false;
                break;
            }
        }
        // 좋은수열의 조건을 만족한다면 dfs
        if (temp) dfs(str + arr[i]);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
 
    // 맨 앞자리는 1일때가 가장 작다
    dfs("1");
    return 0;
}