[백준] 2661번 좋은 수열 (C++)

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

 

문제 설명

좋은 수열이란 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 수열을 뜻한다.
예를 들어 33, 32121323 은 나쁜 수열이고 32, 32123은 좋은 수열이다.

길이가 n인 좋은 수열들을 찾아 그 중 가장 작은 수를 출력한다

 

주요 로직

1. 백트래킹

1,2,3 중 숫자 하나씩을 추가하면서 현 상황에서 좋은 수열인지 확인을 하고 아니라면 stop, 맞다면 계속 탐색한다.

 

2. n의 범위

처음에 go(int num, int size)로 num을 string이 아닌 int로 설정했었다. n의 범위가 80이하이기 때문에 80자리의 수까지 탐색할 수 있어야 하는 데 int는 약 20억 범위이기에 10자리까지만 탐색할 수 있다. 그러므로 int가 아닌 string으로 탐색해야 한다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n;

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

void go(string num, int size){ 
	if(size == n){
		cout << num << "\n";
		exit(0);
	}
	for(int i=1; i<=3; i++){
		string k = num + to_string(i);
		if(check(k)) go(k, size+1);
	}
	return ;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	
	go("",0);

	
	return 0;
}