백준2661 좋은수열

작성일 | In

문제 링크

  • http://icpc.me/2661

문제 출처

  • 1997 전국 본선 중등부1

사용 알고리즘

  • 백트래킹

풀이

간단한 백트래킹 문제입니다.

  1. i번째에 숫자를 하나 넣고
  2. 1 ~ i까지의 수열이 좋은 수열인지 판단합니다.
  3. 좋은 수열이 아니라면 1번으로 이동해서 다른 수를 삽입
  4. 좋은 수열이 맞다면 i를 1 증가시키고 1번으로 이동

위 절차를 거치면 좋은 수열을 뽑을 수 있습니다.
1번 항목에서 1, 2, 3을 순서대로 넣어본다면, 가장 먼저 만들어진 좋은 수열이 최소값이 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int arr[88];
int n;

bool valid(int idx){
	int cnt = 0;
	for(int i=2; i<=idx/2; i++){ //dist
		for(int j=1; j<=idx-i; j++){ //start
			cnt = 0;
			for(int k=j; k<i+j; k++){
				if(i+k > idx) continue;
				if(arr[k] == arr[i+k]) cnt++;
			}
			if(cnt == i) return 0;
		}
	}
	return 1;
}

void f(int idx){
	if(idx > n){
		for(int i=1; i<=n; i++) cout << arr[i];
		exit(0);
	}
	for(int i=1; i<=3; i++){
		if(arr[idx-1] == i) continue;
		arr[idx] = i;
		if(valid(idx)) f(idx+1);
	}
}

int main(){
	cin >> n;
	f(1);
}