[BOJ 2661] 좋은 수열 (Java)

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

2661번: 좋은수열

import java.util.*;

public class P2661 {
	static String ans="";
	static int[] nums= {1,2,3};
	static int N=-1;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		backtracking(0,"");
		System.out.println(ans);
	}
	public static boolean isGood(String s) {
		int len=s.length();
		boolean flag=true;
		for (int i=1; i<=len/2; i++) {
			String second=s.substring(len-i, len);
			String end=s.substring(len-(2*i),len-i);
			if (second.equals(end)) {
				flag=false;
				break;
			}
		}
		return flag;
	}
	public static void backtracking(int cnt, String s) {
		if (cnt==N) {
			ans=s;
			return;
		}
		for (int i=0; i<3; i++) {
			s=s.concat(Integer.toString(nums[i]));
			if (isGood(s)) {
				backtracking(cnt+1, s);
			}
			s=s.substring(0,s.length()-1);
			if (!ans.equals(""))
				break;
		}
	}
}

backtracking을 이용하는 문제.

promising을 조사하는 조건은 마지막 1개, 2개, 3개, ... 와 인접한 1개, 2개, 3개, ... 의 서브스트링이 동일한지 체크해주면 된다. 

다른 분들의 코드를 보니 backtracking 과정에서 더했던 수를 안 빼줘도 된다.

어차피 최소인 값을 구하는 거니까, (cnt==N) 이 부분에서 답을 출력하고 함수를 끝내줘도 되기 때문이다.