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

---

문제풀이

고민을 많이 한 문제다. 문자열 하나 늘릴 때마다 좋은 수열인지 검사하는 방식을 생각했었는데, 생각만 하고 아닌 거 같아서 구현해보지 않았지만.. 이런 방식이 맞았다.

그래서 풀이 방식은 매우 간단하다.

가장 작은 수를 찾아야 하므로 1, 2, 3 순서대로 DFS를 돌며 좋은 수열이 아니면 버리는 방식으로, 즉 백트래킹 방식으로 풀었다.

백 트랙킹은 DFS 방식에서 조금 더 빠른 방법이다. DFS는 맞든 아니 든 일단 끝까지 가는데, 백트래킹은 가던 중 아니면 해당 그래프 탐색을 중지하고 다음 것을 탐색한다.

1. 0번째 숫자에 1을 넣는다. -> 이건 당연히 좋은 수열임

2. 1번째 숫자에 1을 넣는다 -> 검사 결과 좋은 수열이 아님.

3. 1번째 숫자에 2를 넣는다 -> 검사 결과 좋은 수열임 (12)

4. 2번째 숫자에 1을 넣는다 -> 검사 결과 좋은 수열임 (121)

.

.

.

이런 식으로 풀면 된다.

 

좋은 수열 검사하는 것은 2~40자리이니까 복잡도는 별로 높지 않다고 볼 수 있다. 40^2 정도?

좋은 수열이 아닐 경우 되돌아가야 하므로 DFS방식이 적합하다고 생각했다.

 

#include <iostream>
#include <string>

using namespace std;
int n;
string answer;

// 좋은수열인지 아닌지 체크 하는 함수 뒤부터 본다.
// ex) 1231 -> 12 31, 3 1 체크
bool check(string s) {
    int len = s.size()/2;
    for(int i=1; i<=len; i++) {
        string a = "", b = "";
        for(int j=s.size()-1; j>s.size()-1-i; j--) {
            a += s[j];
        }
        for(int j=s.size()-1-i; j>(int)s.size()-i*2-1; j--) {
            b += s[j];
        }
        // cout << a << " " << b << endl;
        if(!a.compare(b))
            return false;
    }
    return true;
}

void Dfs(int cnt, string s) {
	// 이미 정답을 출력 했을경우
    if(!answer.empty())
        return;
    // 정답 길이 일경우 그게 가장 작은 값일것임.. 1, 2, 3 순서대로 늘리니까!
    if(cnt == n) {
        answer = s;
        cout << answer << endl;
        return;
    }

    if(check(s+"1"))
        Dfs(cnt+1, s+"1");
    if(check(s+"2"))
        Dfs(cnt+1, s+"2");
    if(check(s+"3"))
        Dfs(cnt+1, s+"3");
    
}

int main() {
    cin >> n;

    Dfs(0, "");

    return 0;
}

찝찝한 부분은, 맨 처음 정답을 구한 이후 재귀 호출을 바로 중지하고 싶은데 살짝? 야매로 중지시켜주는 느낌이 있다.