[BOJ] 백준 2661 좋은 수열 - Python/Java

문제

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

2661번: 좋은수열

해설

이 문제는 백트랙킹과 그리디 알고리즘을 동시에 사용해서 해결한 문제입니다.

 

우선 문제에서는 1, 2, 3만을 가지고 길이가 N인 좋은 수열들 중 가장 작은 수를 나타내는 수열을 만들어야 하는데요.

 

이를 위해서는 필연적으로 작은 숫자를 우선으로 수열을 만들어보고, 해당 수열이 좋은 수열이면 문제의 조건을 만족할 것이라는 그리디한 선택을 떠올릴 수 있습니다.

 

하지만, 계속해서 그리디한 선택을 했을 때 K번째 지점까지 좋은 수열이었던 녀석이 K+1번째에는 1, 2, 3중에 어떤 수를 넣어도 좋은 수열을 못 만들게 할 수도 있게 되는 것을 주의해야 합니다.

 

예를 들어, N = 7 일 때 가장 작은 좋은 수열은 "1213121"입니다. 하지만 이 숫자를 기반으로 N = 8일 때를 생각해보면 1, 2, 3 어떤 수를 넣어도 좋은 수열 조건이 깨지게 되는 것을 알 수 있습니다.

 

따라서 이 부분에서는 백트랙킹 기법을 이용하여 현재 작은 수(1)부터 좋은 수열을 만들어보고, 이후에 해당 선택으로 좋은 수열을 만들지 못하는 상황이 오면 그 다음으로 작은 수(2)를 넣고, 마찬가지로 3도 넣어보는 식으로 진행을 해야 합니다.

 

다만, 지금까지 만든 수의 마지막 숫자와 현재 덧붙일 숫자는 같을 수 없기 때문에 두 가지 수의 선택지에서 계속하여 그리디와 백트랙킹을 진행하게 될 것입니다.

 

풀이를 보면 더 직관적으로 이해하실 수 있을 것 같습니다.

풀이 - 파이썬

def makeGoodNumber(n, curr):
    global answer
    length = len(curr)
    if length == n:
        answer = int(curr)
        return True # 성공하면 True를 반환

    # 인접한 수가 동일하면 실패
    for x in ['1', '2', '3']:
        # 마지막 숫자와 같은 숫자는 추가해도 불가능
        if x == curr[-1]: continue
        nextNum = curr + x
        flag = True
        for i in range(1, len(nextNum) // 2 + 1):
            p = nextNum[-i:]
            q = nextNum[-2*i:-i]
            if p == q:
                flag = False
                break
        # 뒤에 붙일 수 있는 경우는 최대 두 가지
        if flag:
            # 더 작은 수로 결과값을 만들 수 있으면 그 결과를 리턴
            result = makeGoodNumber(n, nextNum)
            if result: return nextNum
            # 더 작은 수로 실패하면 그 다음 수로 결과를 만들어서 리턴
            else: continue

n = int(input())
answer = int("9" * 80)
makeGoodNumber(n+1, " ")
print(answer)

풀이 - 자바

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

public class B_2661 {
    static int n;
    static String answer;
    static char[] numbers = {'1', '2', '3'};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        makeGoodNumber(n+1, " ");
        System.out.println(answer.substring(1));
    }

    static boolean makeGoodNumber(int size, String curr){
        int length = curr.length();
        if(length == size){
            answer = curr;
            return true;
        }

        // 인접한 수가 동일하면 실패
        for(char x : numbers){
            // 마지막 숫자와 같은 숫자는 불가능
            if(x == curr.charAt(length-1)) continue;

            String nextNum = curr + x;
            boolean flag = true;
            for(int i = 1; i <= nextNum.length() / 2; i++){
                String p = nextNum.substring(length+1-i);
                String q = nextNum.substring(length+1-(2*i), length+1-i);
                if(p.equals(q)){
                    flag = false;
                    break;
                }
            }
            if(flag){
                // 더 작은 수로 결과값을 만들 수 있으면 그 결과를 리턴
                boolean result = makeGoodNumber(size, nextNum);
                if(result) return true;
                else continue;
            }

        }
        return false;
    }
}