[백준] G4 2661 좋은수열 (java)

www.acmicpc.net/problem/2661

2661번: 좋은수열

 

풀이

 

1) 숫자를 담을 StringBuffer 를 생성

2) depth가 N 이 될때 까지 dfs를 돌릴거임

3) StringBuffer의 마지막 글자가 1,2,3 일 경우를 나누어서

4) 좋은 수열인지 체크하여 백트래킹

5) depth가 N이면 StringBuffer를 출력하고 끝

 

 

 

주의사항

 

1) .subString(Start, End) 에서 End는 포함 안됨

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

public class BJ_G4_2661_좋은수열 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N;
	static StringBuffer sb = new StringBuffer();
	static String result;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		dfs(0);
	}

	private static void dfs(int depth) {
		if(isDuplicated(sb)) {
			return;
		}
		if(depth == N) {
			result = sb.toString();
			System.out.println(result);
			System.exit(0);
		}
		
		if(sb.length() == 0) {
			sb.append(1);
			dfs(depth+1);
			sb.deleteCharAt(sb.length()-1); // 마지막 인덱스 삭제
			
			sb.append(2);
			dfs(depth+1);
			sb.deleteCharAt(sb.length()-1); // 마지막 인덱스 삭제
			
			sb.append(3);
			dfs(depth+1);
			sb.deleteCharAt(sb.length()-1); // 마지막 인덱스 삭제
		}else if(sb.charAt(sb.length()-1) == '1') {
			sb.append(2);
			dfs(depth+1);
			sb.deleteCharAt(sb.length()-1); // 마지막 인덱스 삭제
			
			sb.append(3);
			dfs(depth+1);
			sb.deleteCharAt(sb.length()-1); // 마지막 인덱스 삭제
		}else if(sb.charAt(sb.length()-1) == '2') {
			sb.append(1);
			dfs(depth+1);
			sb.deleteCharAt(sb.length()-1); // 마지막 인덱스 삭제
			
			sb.append(3);
			dfs(depth+1);
			sb.deleteCharAt(sb.length()-1); // 마지막 인덱스 삭제
		}else { // sb.charAt(sb.length()-1) == '3'
			sb.append(1);
			dfs(depth+1);
			sb.deleteCharAt(sb.length()-1); // 마지막 인덱스 삭제

			sb.append(2);
			dfs(depth+1);
			sb.deleteCharAt(sb.length()-1); // 마지막 인덱스 삭제
		}
	}

	private static boolean isDuplicated(StringBuffer sb) {
		boolean flag = false;
		for(int i=1; i<=sb.length()/2; i++) {
			int aLast = sb.length();
			int aFirst = sb.length() - i;
			int bFirst = aFirst -i;
			int bLast = aFirst;
			if(sb.substring(aFirst, aLast).equals(sb.substring(bFirst, bLast))) {
				flag = true;
				break;
			}
		}
		return flag; // true면 중복 false면 중복x
	}

	static String src =
			"80";
}

 

 

후기

 

어려울줄 알았으나 생각보다 쉬운 문제였다. 골드4 라고 하기엔 약간 아쉬운 난이도인것 같다.

골드 5였던 뱀이 훨씬 귀찮았다.