[BOJ/JAVA] 백준 2661번 : 좋은수열

2661번: 좋은수열

---

 

• 생각

backtraking 메소드에서 문자열에 1,2,3을 계속 추가시키면서 좋을수열(PossibleNumber 메소드에서 체크)인 수열만 계속 backtraking하다가 수의 길이가 N이면 출력 후 종료(제일 적은 수가 먼저 도착하기 때문)

 

 

• 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		backtracking("");
	}

	private static void backtracking(String s) {
		if (s.length() == N) {
			System.out.println(s);
			System.exit(0);
		}

		for (int i = 1; i <= 3; i++) {
			if (PossibleNumber(s + i))
				backtracking(s + i);
		}
	}

	private static boolean PossibleNumber(String s) {
		int length = s.length();
		for (int i = 1; i <= length/2; i++) {
			String frontString = s.substring(length-i*2, length-i);
			String backString = s.substring(length-i, length);
			if (frontString.equals(backString))
				return false;
		}

		return true;
	}
}