2661번

2661번 - 좋은 수열

로직은 작은 수를 만들으라고 했기 때문에, 1-2-3 순서로 넣어가면서 넣어지면 바로 다음 단계로 넘어가면 된다.

다음 수를 넣을 때는, 우선 기본적으로 이전의 수는 뛰어넘도록 했다. p!=i 인 구문

그 다음으로 체크 함수를 통해서 문자열이 만들어졌을 때, 문자열 길이를 기준으로 반나눠서

끝에서 부터 한개, 끝에서 두개, 이런식으로 비교를 하도록 만들었다.

이때 substr 함수를 써서 string 을 쉽게 다룰 수 있었다.

평소에 substr 함수는 인자를 한개만 넣어서 사용했는데, 두개 넣을 경우 시작점과 갯수를 넣어주면 된다.

처음에 시작점과 끝점을 넣는 줄 알고 풀다가 오류가 발생했다.

<정답 코드>

#include<iostream>
#include<string>
using namespace std;
int n;
bool chk(string str)
{
    int k = (str.size() / 2);
    int size = str.size();
    for (int i = 1; i <= k; i++)
    {
        string front=str, back=str;
        int backstart = size - i;
        int frontstart = backstart-i;
 
        front = front.substr(frontstart, i);
        back = back.substr(backstart, i);
 
        if (front == back)
        {
            return false;
        }
    }
 
    return true;
 
}
void go(string str,int len,int p)
{
    if (len == n)
    {
        cout << str << "\n";
        exit(1);
        return;
    }
 
 
    for (int i = 1; i <= 3; i++)
    {
        char tmp = i + '0';
 
        if (p!=i && chk(str+tmp))
        {
            go(str + tmp, len + 1, i);
        }
        
    }
 
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str = "";
    cin >> n;
 
    go(str,0,-1);
 
    return 0;
}