[algorithm] 백준 - 좋은 수열

이 문제는 두가지 해결책을 내야했다.

1. 좋은 수열을 걸러내는 작업
2. dfs

좋은 수열을 걸러내는 작업

• 비교해야하는 크기
• 비교해야하는 인덱스 위치

1212
123123
12341234

와 같이 (길이 / 2) 만큼의 수열을 비교해야한다는 것을 알 수 있다.

12341233 -- 비교해야하는 수열의 크기가 1일 때

6,7을 비교한다.

12341212 -- 비교해야하는 수열의 크기가 2일 때

45 67을 비교한다.

12345345 -- 비교해야하는 수열의 크기가 3일 때
234 567을 비교한다.

12341234 -- -- 비교해야하는 수열의 크기가 4일 때
0123 4567을 비교한다.

 

이것을 수식으로 표현해보자면, 수열의 크기는 i, 변하는 값은 j로 했을 때
arr[len - 2*i + j]
arr[len - i + j]
로 표현할 수 있다.

bool isGoodNumArray(vector<int> numVector){
    int length = numVector.size();
    for(int i = 1; i <= length / 2; i++){
        string str1 = "", str2 = "";
        for(int j = 0; j < i; j++){
            str1 += to_string(numVector[length - 2*i + j]);
            str2 += to_string(numVector[length -i + j]);
        }
        if(str1.compare(str2) == 0) return false;
    }
    return true;
}

dfs

 1,2,3 중 하나로 이뤄진 수열이다. 최소값을 출력해야하므로,
지속적으로 반복문을 돌면서 start index는 0으로 설정하고 end index는 3으로 설정해야한다.
만약 재귀함수에 진입했을 때 index를 초기화하지 않고 늘려가는 식으로 설정하면

void dfs(int target, vector<int> numVector, int index){
    if(isGoodArray) return;
    if(target == 0){
        isGoodArray = true;
        for(int i = 0; i < numVector.size(); i++){
            cout << numVector[i];
        }
        return;
    }
    if(index == 3) return;
    for(int i = index; i < 3; i++){
        numVector.push_back(numArray[i]);
        if(isGoodNumArray(numVector)){
            dfs(target - 1,index + 1, numVector);
        }
        numVector.pop_back();
    }
}

더 작은 수가 와도 되는 위치에 큰 수가 올 수 있어 최솟값을 출력할 수 없게 된다.

void dfs(int target, vector<int> numVector){
    if(isGoodArray) return;
    if(target == 0){
        isGoodArray = true;
        for(int i = 0; i < numVector.size(); i++){
            cout << numVector[i];
        }
        return;
    }
    for(int i = 0; i < 3; i++){
        numVector.push_back(numArray[i]);
        if(isGoodNumArray(numVector)){
            dfs(target - 1, numVector);
        }
        numVector.pop_back();
    }
}

따라서 반드시 index를 초기화해야한다.

 

전체적인 코드는 이렇다.

// 좋은 수열
#include <iostream>
#include <vector>
using namespace std;

int numArray[]={1,2,3};
bool isGoodArray = false;
bool isGoodNumArray(vector<int> numVector){
    int length = numVector.size();
    for(int i = 1; i <= length / 2; i++){
        string str1 = "", str2 = "";
        for(int j = 0; j < i; j++){
            str1 += to_string(numVector[length - 2*i + j]);
            str2 += to_string(numVector[length -i + j]);
        }
        if(str1.compare(str2) == 0) return false;
    }
    return true;
}
void dfs(int target, vector<int> numVector){
    if(isGoodArray) return;
    if(target == 0){
        isGoodArray = true;
        for(int i = 0; i < numVector.size(); i++){
            cout << numVector[i];
        }
        return;
    }
    for(int i = 0; i < 3; i++){
        numVector.push_back(numArray[i]);
        if(isGoodNumArray(numVector)){
            dfs(target - 1, numVector);
        }
        numVector.pop_back();
    }
}
int main(void){
    int count;
    cin >> count;
    vector<int> numVector;
    dfs(count, numVector);
}

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102910.cpp

jeongdaeun98/algorithm