[백준] 2661번 : 좋은 수열 (C++)

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들 사이에는 빈칸을 두지 않는다.

 

 

 

 

 

 

 

풀이)

// 2661. 좋은 수열
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int n;
vector<int> vec;
 
// 제일 작은 수열이 나오면 그 이후 연산은 불필요하므로
bool fin = false;
 
// 나쁜 수열인지 확인한다.
bool check(int cur)
{
    string temp = "";
    for (int i = 0; i < cur; i++)
    {
        temp += to_string(vec[i]);
    }
    // 해당 수열을 뒤집는다.
    reverse(temp.begin(), temp.end());
    
    // 1부터 길이의 반까지 잘라 같은 수가 있는지 확인한다.
    for (int i = 1; i <= temp.length() / 2; i++)
    {
        string c1 = temp.substr(0, i);
        string c2 = temp.substr(i, i);
 
        if (c1 == c2) return true;
    }
    return false;
}
 
 
void recur(int cur, int prev)
{
    if (fin == true) return;
 
    if (cur > 1 && check(cur) == true) return;
 
    if (cur == n)
    {
        for (int i = 0; i < n; i++)
        {
            cout << vec[i];
        }
        fin = true;
        return;
    }
 
 
    for (int i = 1; i < 4; i++)
    {
        if (i == prev) continue;
        vec[cur] = i;
        recur(cur + 1, i);
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vec.resize(n);
    recur(0, 0);
 
    return 0;
}
 

 

---

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

2661번: 좋은수열