2661 - 좋은 수열

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

2661번: 좋은수열

#include <iostream>
#include <string>
using namespace std;

int N;
string num;

void permutation(const char c, const int cnt)
{
    //조건 만족(제일 먼저 나오는 숫자가 제일 작은 수)

    if (cnt - 1 == N) {
        cout << num << "\n";
        exit(0);
    }

    num += c;

    for (int i = 1; i <= cnt / 2; i++) {
        const string&& a = num.substr(cnt - i, i);
        const string&& b = num.substr(cnt - i * 2, i);
        //나쁜 수열

        if (a == b) {
            num.erase(cnt - 1);
            return;
        }
    }

    for (int i = 1; i <= 3; i++) {
        permutation(i + '0', cnt + 1);
    }

    num.erase(cnt - 1);  //cnt - 1 자리가 성립하지 않을 경우
}

int main(void)
{
    cin >> N;
    for (int i = 1; i <= 3; i++) {
        permutation(i + '0', 1);
    }

    return 0;
}

정답 링크 : https://jaimemin.tistory.com/860

백준 2661번 좋은수열

 

 

재귀함수를 이용하여 풀 수있는 문제였습니다. 코드는 위 링크와 완전 동일합니다.

기본적으로 아래와 같은 방법으로 주어진 자리수의 숫자를 체크합니다.

• 재귀함수를 이용하여 1 + 1 + 1 -> '111' 과 같은 방법으로 모든 숫자를 점검하는 컨셉입니다.
• 하지만 실제로 모든 경우를 체크해볼 필요는 없습니다. 이유는 아래와 같습니다.
• 1 + 1 + 1 이런식으로 체크하기 때문에, 가장 낮은수부터 체크하게끔 돼있습니다.
• 그렇기 때문에, 만일 조건이 충족되는 최초의 숫자가 발견된다면, 그 즉시 프로그램 종료하면 됩니다. 그 숫자가 가장 작기 때문입니다.

​

위 사진과 같이 재귀함수를 이용해 각각의 case를 검사합니다.