백준 2661번 좋은수열

문제 링크입니다: https://www.acmicpc.net/problem/2661

string의 substr 함수를 잘 이용해야하는 백트래킹 문제였습니다.

알고리즘은 아래와 같습니다.

1. 1, 2, 3으로만 이루어지므로 반복문을 통해 1, 2, 3을 더해나갑니다.

2. 조건이 최초로 만족할 경우가 제일 작은 숫자이므로 출력하고 exit(0)를 통해 프로그램을 종료합니다.

3. substr을 이용하여 인접한 부분 문자열이 같은지 확인합니다.

#include <iostream>

#include <string>

using namespace std;

 

int N;

string num;

 

void permutation(char c, int cnt)

{

        //조건 만족(제일 먼저 나오는 숫자가 제일 작은 수)

        if (cnt - 1 == N)

        {

                 cout << num << "\n";

                 exit(0);

        }

 

        num += c;

        for (int i = 1; i <= cnt / 2; i++)

        {

                 string a = num.substr(cnt - i, i);

                 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;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~