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

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

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을 추가한 경우들을 다 살펴보면된다

이때 좋은 수열 판단 기준을 구현하는게 꽤 까다로웠는데, dp개념을 적용해보자.

이전 수열이 좋은 수열이였다면 이후 수열은 추가된 숫자부분만 제외하면 좋은 수열이다. (이 부분은 판단할 필요 없음)

맨 뒤 숫자가 포함된 부분수열만 겹치는게 있는지 판단하면 된다.

부분수열은 substr을 이용하여 구현하였다.

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

int n;
string ans;

bool isGood(string num, int cnt) {
    for(int i=1; i<=cnt/2; i++) {
        string s1 = num.substr(cnt-i, i);
        string s2 = num.substr(cnt-i*2, i);
        
        if(s1==s2)
            return false;
    }
    return true;
}

void recur(string num, int cnt) {
    // 이미 완료되었거나 좋은수열이 아니라면 패스
    if(ans!="")
        return;
    if(!isGood(num, cnt))
        return;
    
    // 갯수 다 채웠으면 반환
    if(cnt == n) {
        ans = num;
        return;
    }
    
    // 재귀 (백트래킹)
    for(int i=0; i<n; i++) {
        recur(num+"1", cnt+1);
        recur(num+"2", cnt+1);
        recur(num+"3", cnt+1);
    }
    
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> n;
    
    recur("", 0);
    
    cout << ans;
    
    return 0;
}

/*
 */