백준 2661 좋은 수열 풀이

문제

&Title
2661번 - 좋은수열

&Question
숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 
길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 
그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 
수열이다.다음은 나쁜 수열의 예이다.3332121323123123213다음은 좋은 수열의 예이다.232321231232123길이가 N인 좋은 
수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 
수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 
좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다. 


&Input
입력은 숫자 N하나로 이루어진다. N은 1 이상 80 
이하이다. 

&Output
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 
길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 
수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 
두지 않는다. 

&Example
-input
7

-output
1213121

요약

• 1, 2, 3 으로 이루어진 수열이 있다
• 연속된 두개의 부분 수열 중 동일한 수열이 있는걸 나쁜 수열이라 한다.
• 나쁜 수열이 없는 좋은 수열의 최솟값을 출력하라

접근

• 일단 세가지 수로 이루어 졌는데 연속으로 같은 숫자는 못쓰인다.(11에서 1, 1 부분 수열이라)
• 뭔가 규칙이 있을것 같다 생각했지만 따로 없었음

• 1213121 여기에서 2라는 숫자가 추가 된다고 생각할때 어떻게 검사해야 할까? 12131212 -> 맨뒤부터 1|2 & 12|12 & 131|212 & 1213|1212 총 len / 2 만큼 검사한다. 그 외의 경우는 이미 이전 경우에 검사가 된것이기 때문이다.(따라서 2가 추가 되는 경우 12

  12 때문에 나쁜 수열이 된다.)

• 이외의 경우가 많으니 4개로 줄여보겠다 1213 -> 1

  3 & 12

  13 를 검사한다. 이외의 경우는 1

  2, 2

  1이다. 이 경우는 모두 n = 2, n = 3일때 검사가 완료되었다.

풀이

1. 검사하는 부분만 알면 풀이자체는 쉽다. 시작은 무조건1로 시작한다. 사전순 가장 앞이기 때문이다.
2. if (depth - 1 == n)이면 문자열 출력후 종료
   1. 인자로 받은 문자를 추가한다
   2. 1~len/2크기만큼 뒤에서 부터 잘라서 두 문자열을 비교한다

       string a = s.substr(depth - i, i);
       string b = s.substr(depth - i * 2, i);
      
       if (a == b)
      

   3. 같은 경우 나쁜 수열이므로 문자를 지워주고 종료
   4. 1~3(이전것과 같은 경우 제외) 재귀를 돌려준다.
   5. 해당 경우의 수가 끝나고도 종료가 되지 않은 것은 해당 선택지가 나쁜 수열인것이므로 문자를 지워주고 종료

소스

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

int n;
string s;

void backtracking(char c, int depth) {
	if (depth - 1 == n) {
		cout << s << endl;
		exit(0);
	}
	s += c;
	for (int i = 1; i <= depth / 2; ++i) {
		string a = s.substr(depth - i, i);
		string b = s.substr(depth - i * 2, i);

		if (a == b) {
			s.erase(depth - 1);
			return;
		}
	}

	for (int i = '1'; i <= '3'; ++i) {
		if (c == i)continue;
		backtracking(i, depth + 1);
	}
	s.erase(depth - 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;

	backtracking('1', 1);
	return 0;
}