[백준,c++] 2661번 - 좋은수열

문제

2661번: 좋은수열

 

코드

#include <iostream>
#include <algorithm>
#include <vector>


using namespace std;


int N;
string ans;
bool flag = false;
bool isvalid(string num){
    int end = num.length()-1;
    for(int i=1; i<num.length(); i++){
        if(end-i<0) return true;
        string num1 = num.substr(end, i);
        string num2 = num.substr(end-i, i);
        if(num1 == num2) return false;
        end--;
    }
    
    return true;
}

void backtracking(int idx, string temp){
    if(!isvalid(temp) || flag) return;
    
    if(idx == N){
        ans = temp;
        flag = true;
        return;
    }
  
    backtracking(idx+1, temp+"1");
    backtracking(idx+1, temp+"2");
    backtracking(idx+1, temp+"3");
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    
    backtracking(0, "");
    cout<<ans;
    
}

 

풀이

백트랙킹 보다는 나쁜 수열인지 좋은 수열인지 판별하는 부분을 구현하기가 까다로웠던 문제였습니다.

[백준/C++] 2661번: 좋은수열 (DFS, 백트랙킹)

해당 부분은 위 블로그의 풀이 방법을 참고했습니다.

인접한 두 개의 부분 수열이 같은지를 검사하면 됩니다. 32121 이라는 수열이 있다고 가정하고 이를 검사하는 과정은 아래와 같습니다.

• 32121  -> 2와 1은 다르기 때문에 통과
• 32121 -> 21과 21은 같기 때문에 실패