[백준/Java] 2661: 좋은 수열

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

 

 

조건

• TimeLimit = 1s
• 수열은 길이가 n이고, '1,2,3'으로만 이루어져있다 (n<=80)
• 나쁜 수열 -> 수열 내에서, 인접한 두 부분수열의 길이와 원소가 동일한 경우
• 길이가 n인 좋은 수열중, 가장 작은 수열을 출력하여라

 

풀이

• 완전탐색 -> 백트래킹
  • 1,2,3을 n개만큼 나열하는 것과 같다(순열)
  • 따라서 3**n만큼의 시간복잡도가 발생하는데.. 강력한 가지치기가 없다면 불가능하다
  • 바로 이전에 선택한 수만 안고르더라도 시간복잡도는 2**n으로 줄어든다. 가지치기 잘 하면 될수도?
  • 1부터 탐색한다면 제일 처음 찾는 수열이 제일 작은 수열이 되므로 정렬 및 추가 탐색은 필요없다
  • 검토해야하는 블럭의 최대 길이는, 현재 size/2 크기이다(해당 길이를 넘어가면 인접한 동일한 길이의 부분수열이 없기 때문)
  • 따라서 해당 조건을 만족하는, 가장 마지막에 추가한 숫자가 포함된 블럭만 탐색해보자

 

코드

import java.io.*;
	import java.util.*;

public class Main {

	static int n;
	static int[] selected;
	static boolean ans = false;
	static StringBuilder sb = new StringBuilder();


	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());


		// dfs
		selected = new int[n];
		dfs(0, 0);

		// result
		System.out.print(sb);
	}




	static void dfs(int size, int pre) {

		if (ans) return;

		if (size == n) {
			for (int i=0; i<n; i++) sb.append(selected[i]);
			ans = true;
			return;
		}

		for (int i=1; i<=3; i++) {

			if (i==pre) continue;

			selected[size] = i;
			if (!validate(size+1)) continue; // 마지막 값을 추가했으므로 size+1을 검사

			dfs(size+1, i);
			if (ans) return;

		}

	}



	static boolean validate(int size) {

		// 비교할 길이(2부터 size/2까지)
		for (int l=2; l<=size/2; l++) {

			boolean isSame = true;

			// 마지막 값이 포함된 블럭만 조회한다
			// 즉, 마지막 추가된 값부터, l까지만 탐색하면 된다. 앞에서부터 할 필요가 없다
			for (int stt=0; stt<l; stt++) {

				if (selected[size - stt -1] != selected[size - stt - l -1]) {
					isSame = false;
					break;
				}

			}

			// 하나라도 동일한게 있다면 false를 return
			if (isSame) return false;
		}

		return true;
	}


}