[백준 2661번] 좋은수열

[백준 2661번] 좋은수열

www.acmicpc.net/problem/2661

2661번: 좋은수열

 

 

 문제

 숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

 다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

 다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

 길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

 

 입력

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

 

 출력

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

 

 

 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, arr[81];

bool check(int a){
	for(int i=1;i<=a/2;i++){
		for(int j=1;j<=a-i*2+1;j++){
			bool flag = true;
			for(int k=0;k<i;k++){
				if(arr[j+k] != arr[j+i+k]) flag = false;
			}
			if(flag == true){
				return false;
			}
		}
	}
	return true;
}

void ff(int i){
	if(i==N+1){
		if(check(i-1)){
			for(int k=1;k<=N;k++){
				cout << arr[k];
			}
			exit(0);
		}
		return;
	}
	
	for(int j=1;j<=3;j++){
		if(arr[i-1] == j) continue;
		arr[i] = j;
		if(check(i)) ff(i+1);
		// ff(i+1);
	}
	
	
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	arr[0] = 2;
	ff(1);
	return 0;
}

 수열을 arr 배열에 차례대로 넣어간다. 일단 좋은 수열중 가장 작은 수열은 제일 앞자리가 1일 것이고, 연속해서 같은 수가 나오면 안되기 때문에 continue 처리했다. 처음에는 길이가 N이 되고나면 check함수를 돌려 좋은 수열인지 아닌지 판단하게 했는데 이렇게 하면 불필요한 확인이 너무 많이 된다. 따라서 arr에 숫자를 넣을 때마다 check를 함으로써 시간초과를 해결할 수 있었다. 작은 수 부터 차례대로 올라가기 때문에 좋은 수열을 하나 발견하는 순간 좋은 수열 중 가작 작은 수가 되기 때문에 exit처리를 해주었다.

 좋은 수열인지 아닌지 판단하는 check함수에서 3중 반복문으로 구현했는데 string을 이용한다면 좀 더 간단하게 구현할 수 있을 것 같은 생각이 들었다.

 아무튼 한방에 풀려서 만족한 문제이다.