[Algorithm] Baekjoon 2661번 : 좋은수열

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

2661번: 좋은수열

int targetCount = 0;
string result = "";
bool isCheck = false;
 
bool check(string s)
{
    for (int i = 1; i <= s.size() / 2; i++)
    {
        string left = s.substr(s.size() - i * 2, i);
        string right = s.substr(s.size() - i, i);
 
        if (left == right) return false;
    }
 
    return true;
}
 
 
void DFS(string s, int count)
{
    if (s.size() == targetCount)
    {
        isCheck = true;
        result = s;
        return;
    }
 
    for (int i = 1; i <= 3; i++)
    {
        string temp = s;
        temp += i + '0';
 
        if (check(temp))
        {
            DFS(temp, count + 1);
        }
 
        if (isCheck) return;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
 
    cin >> n;
    targetCount = n;
 
    DFS("", 0);
 
    cout << result << endl;
}

 

숫자하나씩 추가할때마다 뒤에서부터 s.size() / 2까지 구간별 검사를 해서 한번이라도 일치하면 false를 리턴한다.

규칙찾는게 어렵긴한데, 어떻게든 찾으면 구현은 이제 무난하게 하는것같다.