[문제] 백준 2661번 좋은수열

www.acmicpc.net/problem/2661

2661번: 좋은수열

내 풀이

 

코드만 보면 쉽게 푼 것 같지만, 쉽게 풀지는 못했었다.

수열을 String으로 할 생각을 안하고 배열로 하려고 했어서 실수도 계속했고, 부분수열끼리 비교할 때도 계속 실수했다.

substring을 통해 간단히 비교할 수 있었다.

public class BOJ_2661 {
	static int N;
	static int[] arr;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		String s= "1";	// 처음 1로 시작
		good(1,s);
	}
	// 수열 s가 좋은 수열인지 판별하는 함수 
	static boolean isGood(String s) {
		int len = s.length();
		int start = len-1;	
		int end = len;
		for(int i=1;i<=len/2;i++) {	// 길이의 절반만큼 비교하게 됨.
			if(s.substring(start,end).equals(s.substring(start-i,end-i)))// 부분 문자열 비교. 
					return false;
			start--;	// 길이를 하나씩 늘려가면서 비교
		}
		return true;
	}
	// 좋은 수열 찾는 함ㅅ
	static void good(int len, String s) {
		if(len == N) {	
			System.out.println(s);
			System.exit(0);
		}
		
		for(int i=1;i<=3;i++) {
			if(isGood(s+i)) {	// 1,2,3 중 하나를 추가했을 때 좋은 수열이면 재귀
				good(len+1, s+i);	
			}
		}
	}
}