[알고리즘] Java / 백준 / 좋은 수열 / 2661

[알고리즘] Java / 백준 / 좋은 수열 / 2661

문제

문제 링크

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

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

• 33
• 3323 2121
  
• 123123213

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

• 2
• 32
• 32123
• 1232123

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

입력

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

출력

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

접근 방식

1, 2, 3 수 중 하나를 선택하여 N 길이의 수열을 만들면서 좋은 수열인지 확인한다.

기존 수열에 1, 2, 3 순서로 수를 뒤에 붙여서 새로운 수열을 만들고 이 수열이 좋은 수열이고 N의 길이라면 이는 N 길이의 좋은 수열 중 최소인 수일 것이다.

따라서 첫 번째로 N길이의 좋은 수열을 찾으면 나머지 연산을 모두 종료 시키고 첫 번째로 찾은 좋은 수열을 출력한다.

좋은 수열인지를 검사하는 방법은 수열을 입력받고 길이를 1부터 점점 늘려가며 수열의 처음부터 끝까지 해당 길이의 붙어있는 부분 수열을 비교하여 하나라도 같다면 나쁜 수열이고 모든 검사를 통과하면 좋은 수열이다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_2661 {

	static String answer;
	static int N;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		answer = "";
		go("");
		
		System.out.println(answer);
	
	}
	
	public static void go(String temp) {
		
		if(answer != "") return;
		
		if(temp.length() == N) {
			answer = temp;
			return;
		}
		
		for(int i=1;i<=3;i++) {
			if(check(temp+i)) {
				go(temp+i);
			}
		}
	}
	
	// 입력받은 매개변수가 좋은 수열인지 확인하는 함수
	public static boolean check(String value) {
		for(int i=1;i<=value.length()/2;i++) {
			for(int j=0;j<=value.length()-i*2;j++) {
				if(value.substring(j,j+i).equals(value.substring(j+i,j+i*2))) return false;
			}
		}
		return true;
	}

}