[JAVA]백준_2661_좋은순열

문제링크

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

2661번: 좋은수열

 

 

 

import java.util.Scanner;

public class Main {
	static int N;
	static String res="";
	static boolean isTrue;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		dfs("1",1); //1번째 위치에 1 넣기
		
		//System.out.println(result);
	}

	static void dfs(String res,int cnt) {//좋은 순열 인 것들만 넘어옴
		if(isTrue) return;
		if(cnt == N) {
			System.out.println(res);
			isTrue = true;
			return;
		}
		
		for(int i=1;i<=3;i++) {
			if(isPossible(res+i)) dfs(res+i,cnt+1);
		}
	}
	

	static boolean isPossible(String res) {
		//전체 길이의 반틈만 비교
		int div = res.length() /2;
		int beginIndex = res.length() -1; //전체index 바로 앞에꺼
		int endIndex = res.length(); //마지막 index
		for(int i=1;i<=div;i++) { //1부터 div길이까지 비교해주기
			if(res.substring(beginIndex-i, endIndex-i).equals(res.substring(beginIndex, endIndex))) return false;
			beginIndex -=1;
		}
		return true;
	}
}

 

백트래킹문제이다.

맨처음에 배열을 만들어서 풀려고 했는데 N = 80이라서 80자리 Integer는 비교를 못할 것 같았다.

그래서 String으로 비교하였다.

좋은 순열을 찾기위해서는 1개,2개,,,N개 까지 겹치는 순열?이 있는지 확인을 해봐야했다.

N개 까지는 할 필요 없고 N/2만큼만 진행해주면 된다

123123   -> 123 / 123 이렇게만 비교해주면 되기 때문이다.

그래서 여기까지는 쉽게 알아냈는데 자릿수마다 비교해주는거 구현하는게 힘들었당

포문 3개 돌릴려다가 이건 아닌거 같아서 구글에 검색해보았다

mygumi.tistory.com/213 이 분 글 보고 구현하는 법 배웠다.