백준 2661 좋은 수열 (java, backtracking)

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

2661번: 좋은수열

 

백트래킹도 백트래킹이지만, 문자열이랑도 관련이 있는 문제라고 볼 수 있다.

 

그 이유는 N의 범위가 80까지 주어지기 때문에,

 

Integer나 Long으로 비비다가는(?) NumberFormat Exception을 만날 수 있기 때문이다.

 

참고로 Java의 Long 범위는 아래와 같다.

 

-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

 

Big Integer 따위도 사용할 수 있겠지만,

 

굳이 그렇게까지 갈 필요는 없을 것 같아서 StringBuilder로 풀었다.

 

 

 

핵심 아이디어는 다음과 같다.

우측 끝에서부터 1 또는 2 또는 3을 추가하면서 진행한다.

 

① 1자리:1자리 비교

② 2자리:2자리 비교

③ 3자리:3자리 비교

...

 

( 조건: 인접한 두 부분 수열이 동일하면 안 됨 )

 

 

 

코드로 표현하면 아래와 같다.

int area = 2;
boolean check = true;
while (area <= next.length()){
    int half = area/2;

    // right
    int start = next.length()-half; // l:6, area:2 --> 6-1 --> 5 ||| l:6, area: 4 --> 6-2 --> 4
    int end = next.length();
    String right = next.substring(start, end);

    // left
    end = start;
    start = end-half;
    String left = next.substring(start, end);

    if(left.equals(right)){ // 두 수가 같다? 다음 것
        check = false;
        break;
    }

    area += 2; // 2, 4, 6, 8, ...
}

관심가져야 할 부분은 area가 짝수 +2 단위로 늘어난다는 점이다.

 

변수 area는 부분 수열 2개를 포함한 영역을 나타낸다. 인덱스가 아니라 길이이다. ( 6->3+3, 4->2+2, 2->1+1)

 

계산의 효율을 위해 오른쪽 부분 수열인 right를 먼저 구하고 그 다음 왼쪽으로 슬라이딩 윈도우를 이동하듯 영역을 옮겨 왼쪽 부분 수열 left를 구한다.

 

바로 이 부분,

// right
int start = next.length()-half; // l:6, area:2 --> 6-1 --> 5 ||| l:6, area: 4 --> 6-2 --> 4
int end = next.length();
String right = next.substring(start, end);

// left
end = start;
start = end-half;
String left = next.substring(start, end);

 

위처럼 좌측:우측을 구해서 비교하면 된다.

if(left.equals(right)){ // 두 수가 같다? 다음 것
    check = false;
    break;
}

두 수가 같으면 정답 후보가 될 수 없으므로, 영역을 더 확장하여 비교할 필요 없이 반복문을 종료한다.

 

반복문이 끝나고 정답 후보가 될 수 있다면 백트래킹을 진행한다. 아니라면 그냥 종료한다.

if(check) backTracking(next,lth+1);
if(stop) return;

아래의 stop 플래그는 정답을 찾아낼 시에 모든 재귀층을 무너뜨릴 플래그이다.

 

저번에 러버덕(18233)도 그렇고 내가 백트래킹 짜면 이상하게 재귀층 부수는 경우가 많다.

 

우드 블럭 빼기 놀이하다가 와르르되는 느낌

 

 

 

마지막으로 답을 하나만 찾으면 stop 플래그가 켜지게 되는 점인데, 조금만 생각해보면 그 이유를 알 수 있다.

if(n <= lth){
    ans = str;
    stop = true;
    return;
}

왜냐하면 백트래킹을 돌리기 위한 후보군을 구하기 위한 for문에서 i=1부터 시작하게 되고,

 

다시 말하면 이는 항상 최솟값을 가장 먼저 고려하면서 백트래킹을 진행하기 때문이다.

 

그래서 제일 먼저 만들어지는 좋은 수열이 바로 답이 되는 수열이다.

 

 

 

아래는 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n;
    static StringBuilder ans;
    static boolean stop;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        ans = new StringBuilder();
        stop = false;
        backTracking(new StringBuilder("1"), 1);
        System.out.print(ans);
    }

    static void backTracking(StringBuilder str, int lth){
        if(n <= lth){
            ans = str;
            stop = true;
            return;
        }

        for(int i=1; i<4; ++i){
            StringBuilder next = new StringBuilder(str);
            next.append(i);

            int area = 2;
            boolean check = true;
            while (area <= next.length()){
                int half = area/2;

                // right
                int start = next.length()-half; // l:6, area:2 --> 6-1 --> 5 ||| l:6, area: 4 --> 6-2 --> 4
                int end = next.length();
                String right = next.substring(start, end);

                // left
                end = start;
                start = end-half;
                String left = next.substring(start, end);

                if(left.equals(right)){ // 두 수가 같다? 다음 것
                    check = false;
                    break;
                }

                area += 2; // 2, 4, 6, 8, ...
            }

            if(check) backTracking(next,lth+1);
            if(stop) return;

        }

    }
}

 

 

 

고민 시간이 은근히 길었는데, 고려할 부분이 많았던 백트래킹 문제인 듯하다.