D+11 백준 2661 좋은수열

백준 2661 좋은수열 - 골드 4

백트래킹 last 문제.. 1시간 40분 걸렸넴..ㅎㅎ

아이디어는 다음과 같아요.

1. 큰 재귀 안에 작은 재귀 

- 큰재귀는 1, 2, 3을 계속해서 더해가면서 n자리가 될때까지 모든 수를 만들어가는거에요.

- 작은 재귀는 중간에 만들어진숫자가 나쁜수열을 가지고있는지 판별하는거에요.

2. 좋은수열/나쁜수열 판별방법

ex) 1212가 나쁜수열인지 확인하는 방법 

     1) 12"1" vs "2"  비교 <-- ok

     2) "12" vs "12" 비교  <-- 나쁜수열

   * 즉 숫자를 뒤부터 한칸씩 떼어내어 숫자를 만든다음. 크기만큼 이미만들어진 앞의 숫자와 비교한다.

   * 추가로 n자리 숫자가 다 만들어진다음에 나쁜수열을 찾으려고하면 안된다. 중간에 숫자를 만들어가면서 해야한다.

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

2661번: 좋은수열

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

public class Main {
    
    static int n =0;
    static boolean flag = false; //n자리 좋은 수열이 만들어졌는지 체크
    static boolean checkreturn = false; //나쁜수열인지 체크
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        String num = "";
        findminNum(num); //가장작은 좋은수열찾기
    
    }//main method end
    
    private static void findminNum(String num){
        if(num.length()==n){ //n자리 숫자가 만들어지면
            System.out.println(num);
            flag = true;
            return;
        }
        for(int i=1; i<=3; i++){
            String compair = i+"";
            checkreturn = false;
            check(num,compair);
            if(!checkreturn){ //좋은수열이면
                findminNum(num+compair);
                if(flag){
                    break;
                }
            }
        }
    }//find method end
    private static void check(String num,String compair){ //좋은수열인지 판별
        int numln = num.length();
        int compairln = compair.length();
        if(numln-compairln>=0){ //크거나 같을때만
            if(num.substring(numln-compairln,numln).equals(compair)){//같으면
                checkreturn =  true; //나쁜수열
            }else{
                check(num.substring(0,numln-1),num.substring(numln-1,numln)+compair);
            }
        }
  
    }
}//class end