[백준][C++] 2661번: 좋은수열 <182>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

2661번: 좋은수열

 

생각의 흐름

이번 문제는 DFS 탐색을 진행하다가, 불가능한 경우가 나오면 더이상의 탐색 진행을 하지않고 바로 반환하는 백트래킹 문제이다.

 

어떠한 수열이 주어질때 "나쁜수열" 인지를 파악하는것 이 핵심이다.

다만 완전탐색 방식으로 길이가 N인 모든 수열의 경우를 만들고 "나쁜수열"인지 파악하는것은 시간초과 하게 된다.

N은 최대 80까지 가능한데, 길이가 1인 비교, 2인 비교, 3인 비교 ... 40인 비교 를 전부 진행하려면 O(N!)의 시간이 걸리게 된다.

이는 어마어마한 시간이 걸리게 된다.

 

이 문제의 핵심은 다음과 같다!

 

이미 "나쁜수열"로 판정된 수열 뒤에 어떠한 숫자를 더해도 "나쁜수열" 이 된다. 다음 예를 살펴보자.

이미 32121 에서 2121 때문에 "나쁜 수열" 임이 판정났다. 뒤에 어떤 수를 더 추가해도 나쁜 수열이 된다.

=> 백트래킹의 조건에 만족한다. 이미 "나쁜 수열" 임이 판정나면 더이상의 DFS 탐색을 진행하지 않고 return 한다.

 

따라서 답이될 "좋은 수열"은

어떤 수열 ( . . . ) 을 A 라고 했을때, A가 "나쁜 수열"이 아니라면(= 좋은수열)

A 맨 뒤에 1, 2, 3 중 하나를 추가 했을때 좋은 수열인지 파악하면 된다. 이미 A가 "좋은 수열" 인것은 판명 나있다.

 

따라서 맨뒤를 기준으로 전체 길이 N 의 절반인 N/2 까지 "나쁜 수열" 인지? 아닌지? 만 판단하면 된다.

다음 그림은 이미 "좋은수열" 임이 판명된 "12131" 의 맨 뒤에 2를 추가한 case 이다.

나의 코드

#include <bits/stdc++.h>
using namespace std;

int N;

bool isBad(string str){
    int len = str.length();
    int half = len / 2;

    for(int i = 1; i <= half; i++){
        string first = str.substr(len-(i*2), i);
        string second = str.substr(len - i, i);
        if(first == second){
            return true;
        }
    }
    return false;
}

void DFS(int index, string str){
    if(isBad(str)){
        return;
    }
    if(index == N){
        cout << str << "\n";
        exit(0);
    }
    DFS(index + 1, str + '1');
    DFS(index + 1, str + '2');
    DFS(index + 1, str + '3');
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    DFS(0, "");


    return 0;
}