[백준_2661번] 좋은수열

https://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 이하이다.

 

[코드]

import java.util.Scanner;

public class BaekJoon_2661 {
	public static int n;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		dfs("");
	}

	public static void dfs(String num) {
		/*
		 * 만들어진 문자열의 길이가 n과 같아지면 
		 * 해당 문자열을 출력하고 프로그램을 강제종료 한다.
		 * 뮨자열은 1~3 순서대로 숫자가 추가되기 때문에 
		 * 제일 먼저 n 길이로 만들어진 문자열이 가장 작은 숫자가 된다.
		 */
		if(num.length()==n) {
			System.out.println(num);
			System.exit(0);
		}
		
		// 백트래킹
		for(int i=1;i<=3;i++) {
			// 만들어진 문자열이 좋은 수열이라면 재귀호출
			if(check(num+i))
					dfs(num+i);
		}
	}
	
	/*
	 * 해당 문자열이 좋은 수열인지 판단하는 함수
	 * 길이가 n인 수열에서 인접하면서 동일한 수열이 만들어질 수 있는 경우는
	 * 수열의 길이가 최소 1부터 최대 n/2인 경우 발생한다.
	 * 
	 * 따라서 앞의 n/2개의 수와 뒤의 n/2수가 동일한지 비교하여
	 * 좋은 수열인지 판별할 수 있다.
	 */
	public static boolean check(String str) {
		for(int i=1;i<=str.length()/2;i++) {
			String front_str=str.substring(str.length()-i-i,str.length()-i);
			String back_str=str.substring(str.length()-i,str.length());
			
			if(front_str.equals(back_str))
				return false;
		}
		return true;
	}
}

 

[고찰]

 이번 문제 또한 백트래킹으로 1, 2, 3 숫자를 사용하여 만들수 있는 모든 수열을 만든 후, 해당 수열이 좋은 수열인지 판별하는 방식으로 해결할 수 있다. 백트래킹을 사용한다는 것은 쉽게 떠올릴 수 있었지만 어떻게 해당 수열이 좋은 수열인지 판별하는 아이디어는 떠오르지 않아 다른 사람의 코드를 참고하여 해결하였다. 

 길이가 n인 수열에서 인접하면서 동일한 수열이 만들어질 수 있는 경우는 수열의 길이가 최소 1부터 최대 n/2인 경우 발생할 수 있기 때문에 앞의 n/2개의 수와 뒤의 n/2수가 동일한지 비교하여 좋은 수열인지 판별할 수 있다. 이렇게 판별한 수열이 입력받은 n의 길이가 된다면 처음 만들어진 수가 제일 작은 수가 되기 때문에 해당 수를 출력하고 프로그램을 강제종료 시켜주어야 한다.