[devmoon] 골드4 백준 - 2661 좋은 수열

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

2661번: 좋은수열

1. 유형

순열, 백트래킹

 

2. 시뮬레이션

1. N자리로 만들 수 있는 수를 순열을 구한다
2. 한자리씩 추가할때마다, 반복하는 부분이 있는지 파악한다
3. 만약 반복이 되면 그 자리에서 return한다 (백트래킹)

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
	static String ANS;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = stoi(st.nextToken());
		String s = "1";
		dfs("1", N);
		System.out.println(ANS);
	}

	static boolean dfs(String str, int N) {
		if(str.length() == N) {
			ANS = str;
			return true;
		}
		for(int i=1; i<=3; i++) {
			String s = str + String.valueOf(i);
			int start=s.length()-1;
			int end=s.length();
			boolean pass=false;
			for(int j=1; j<=s.length()/2; j++) {
				String sub1 = s.substring(start, end);
				String sub2 = s.substring(start-j, start);
				if(sub1.equals(sub2)) {
					pass=true;
					break;
				}
				start-=1;
			}
			if(!pass) {
				if(dfs(s, N)) return true;
			}
		}
		return false;
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}