[백준/c++] 2661번: 좋은수열

 

 

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

2661번: 좋은수열

 

나올 수 있는 모든 수열을 만들어서 나중에 이게 나쁜 수열인지 좋은 수열인지 체크하는 건 시간 초과가 발생한다.

그래서 아무리 생각해도 어떻게 하면 좋을지 모르겠어서 다른 사람들의 코드를 확인했다.

 

이 분들은 수열을 모두 만들어서 하는게 아니라 하나씩(1,2,3) 붙여나가면서 그때마다 나쁜 수열인지 체크를 했다. 나쁜 수열이면 바로 끝내고 아니면 DFS를 통해서 계속해서 문자를 붙이도록 했다. 그래서 안 되는 애는 바로바로 없애는 방식이라 연산을 덜 할 수 있게 되었다.

 

이 문제를 꼭 기억해서 나중에도 활용할 수 있도록 해야겠다. (모든 경우를 만들고 체크 X / 만들면서 체크 O)

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int n;
bool finish = false;

bool isBad(string s){
    int size = s.size();
    int len = s.size()-1;
    for(int i=1; i<=size/2; i++){
        string s1 = s.substr(len-i, i);
        string s2 = s.substr(len, i);
        if(s1 == s2) return true;
        len--;
    }
    return false;
}

void DFS(int cnt, string result){
    if(finish) return;  //끝났으면 패스
    if(isBad(result)) return; //나쁜 수열이므로 바로 패스
    if(cnt == n){ //N자리 수열 완성
        cout << result << '\n';
        finish = true;
        return;
    }
    DFS(cnt+1, result + '1');
    DFS(cnt+1, result + '2');
    DFS(cnt+1, result + '3');
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    DFS(0, "");
    return 0;
}