[C/C++] 코드업(codeup) 4434번 좋은 수열

▽문제 바로가기

https://codeup.kr/problem.php?id=4434

좋은 수열

---

입력

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

 

출력

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

수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

 

문제 풀이

 

좋은 수열들 중에서 가장 작은 수를 출력하는 문제입니다.

탐색할 때 1부터 차례대로 탐색하면 되겠습니다.

원하는 길이만큼 탐색이 끝나면 즉시 종료해주면 됩니다. 이때 종료하지 않으면 좋은 수열들 중에서 가장 큰 수까지 탐색하게 됩니다.

 

좋은 수열인지 아닌지 판별을 해야 합니다.

예를 들어 길이가 4인 배열이 있다고 가정하면 [0][1][2][3]에서 2와 3을 비교하여 같으면 나쁜 수열입니다.

또한 [0][1]과 [2][3]이 같으면 나쁜 수열입니다.

 

#include <stdio.h>

using namespace std;

int n;	//입력받을 정수n 
int arr[81] = {0,};	//정답 배열
bool check = false;

//좋은 수열인가?
bool isPromising(int i, int k){
	int mid = i/2;
	arr[i-1] = k;
	
	for(int a=1;a<=mid;a++){
		int c=0;
		for(int b=0;b<a;b++){
			if(arr[i-b-1]==arr[i-a-b-1]) c++;
		}
		if(c==a) return false;
	}
	return true;
}

//백트래킹
void backtracking(int i){
	if(i==n){
		check = true;
		return;
	}
	
	for(int k=1;k<=3;k++){
		if(check) break;	//좋은 수열 찾으면 멈춤
		if(isPromising(i+1, k)){
			backtracking(i+1);
		}
	}
	
}

int main(){
	
	scanf("%d", &n);
	
	//백트래킹
	backtracking(0);
	
	for(int i=0;i<n;i++) printf("%d", arr[i]);
	
	return 0;
}