[DFS] 2661번 좋은수열

2661번 좋은수열

 

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

 

문제

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열 1213121이다.

 

입력

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

 

출력

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

 

예제 입력

7

 

예제 출력

1213121

 

해결방법

DFS + 백트래킹으로 가장 먼저 나오는 답을 출력하는 문제이다

 

좋은수열은 같은 수열이 반복되지 않아야 한다

그리고 좋은수열 중 가장 작은 값을 찾아야한다

 

백트래킹을 위해 Vector 를 활용하였다

벡터에 1,2,3 중 하나의 값을 넣은 뒤, 만약 좋은수열의 조건에 맞다면 재귀를 통해 탐색을 진행한다

만약 좋은수열의 조건에 맞지 않다면 벡터에서 값을 뺀 뒤, 다음 값으로 넘어간다

for(int i=1; i<=3; i++){
    v.push_back(i);
    
    if(is_goodPermutation())
        dfs(cnt+1);
        
    v.pop_back();
}

 

좋은수열의 조건을 확인하는 함수이다

만약 수열이 1 2 1 3 이라면 3 1 , 12 13 을 비교해야한다

i : 비교할 수열의 자리수

j : i 자리수 만큼 반복하여 수열을 만듬

bool is_goodPermutation(){
    int len = (int) v.size();
    
    for(int i=1; i<=len/2; i++){
        string s1 = "";
        string s2 = "";
        
        for(int j=0; j<i; j++){
            s1 += to_string(v[len - (2*i) + j]);
            s2 += to_string(v[len - i + j]);
        }
        if(s1 == s2) return false;
    }
    return true;
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 80
#define INF 987654321
using namespace std;

int n;
vector<int> v;

// 좋은 수열인지 확인하는 함수
bool is_goodPermutation(){
    int len = (int) v.size();
    
    // i = 비교할 수열의 자리수
    // 만약 길이가 4라면 1자리, 2자리 수열을 비교해야함
    for(int i=1; i<=len/2; i++){
        string s1 = "";
        string s2 = "";
        
        // i 자리 길이의 수열을 만듬
        for(int j=0; j<i; j++){
            s1 += to_string(v[len - (2*i) + j]);
            s2 += to_string(v[len - i + j]);
        }
        
        // 만약 두개의 수열이 같다면 좋은 수열이 아님
        if(s1 == s2) return false;
    }
    return true;
}

void dfs(int cnt){
    // 좋은 수열의 조건을 가진 채로 cnt == n 이라면
    if(cnt == n){
        for(int i=0; i<v.size(); i++){
            cout << v[i];
        }
        cout << "\n";
        exit(0);
    }
    
    // 1,2,3 의 숫자를 넣어보고
    // 만약 좋은 수열의 조건에 만족한다면 DFS 진행
    for(int i=1; i<=3; i++){
        v.push_back(i);
        
        if(is_goodPermutation())
            dfs(cnt+1);
            
        v.pop_back();
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    dfs(0);
    return 0;
}