[Python] 2661번 좋은수열

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

2661번: 좋은수열

---

 

22/10/06

 

 

전형적인 백트래킹 문제로, 좋은 수열이 되는 조건을 잘 따라가며 시뮬레이션하면 되는 문제이다.

---

 

문제 접근 방식:

 

 

문제를 해설하기에 앞서, 먼저 N = 8일 때의 찾는 과정을 도식화한 그림을 보자.

우리는 좋은 수열 중 가장 작은 수열을 찾는 것이 목적이다.

 

이 그림은 이를 찾기 위해 3가지 조건을 지키면서 탐색을 진행하는 과정을 나타낸 것으로, 3가지 조건은 다음과 같다.

1. 가장 작은 수열을 찾는 것이므로, 방문하는 숫자는 방문 되지 않은 숫자들 중에서 가장 작은 숫자로 정해진다.

2. 만약 방문한 숫자가 나쁜 수열의 조건을 만족시키면 Backtrack을 진행한다.

3. 만약 길이가 우리가 원하는 길이이고, 좋은 수열이면 종료한다.

 

숫자들마다 방문처리를 해줘야 하므로, 어떤 숫자가 나오면 그 숫자를 check_set이라는 set에 담기로 결정했다.

 

또한, 어떤 숫자가 좋은 수열인지 나쁜 수열인지 판단하는 is_good함수를 구현하기로 했다.

 

이 is_good함수의 동작 원리는 다음과 같다.

 

1. 인접한 두개의 부분 수열이 동일한 것이 있으면 나쁜 수열에 해당한다.
때문에 부분 수열의 길이를 정해두고 반복하여 판단한다.
이때, 가능한 부분 수열의 길이는 1부터 (원래 수열의 길이)//2까지 이다.
(인접한 두개의 부분 수열이 동일하도록 하는 부분 수열의 최대 길이는 (원래 수열의 길이)//2이기 때문임)

2. 부분 수열의 길이를 정해두면, 부분 수열이 시작하는 위치를 정해두어 반복문으로 판단한다.
이때, 반복하는 횟수와 그 위치는 (수열의 길이) - (부분 수열의 길이)*2만큼 반복한다.

 

뒤에 1을 붙이는 과정을 op_1, 2를 붙이는 것을 op_2, 3을 붙이는 것을 op_3이라고 했으며, backtrack을 하는 연산은 rev_op라고 지정해두었다.

 

또한, 지금까지 어떤 연산을 거쳤는지를 저장하는 용도로 operation_stack을 하나 만들어주었다.

 

위의 조건 중 첫 번째 조건에 따르면 방문되지 않는 숫자들 중에서 가장 작은 숫자를 방문해야 하므로, 기본적으로 op_1을 먼저 실행한다. 이후, operation_stack에 op_1을 실행했다는 정보를 담고, check_set에 방문처리를 해준다.

 

우리는 backtrack을 진행하면 이미 방문한 숫자를 다시 방문한다는 사실을 잘 알고 있으므로, 조건문으로 2가지를 나눈다.

1. 지금 현재 숫자가 이미 check_set에 있는 경우
이 경우는 이미 방문한 숫자를 다시 방문한 경우이므로, backtrack을 한 번 한 경우이다.

2. 지금 현재 숫자가 check_set에 없는 경우
이 경우는 위에서 작성한 것처럼 기본적으로 첫번째 조건에 따라, 현재 숫자를 방문 처리를 해주고, op_1을 먼저 실행하고 그 정보를 저장해주면 된다.(operation_stack에 넣는다)

만약 어떤 숫자가 is_good을 통과하지 못하면, backtrack을 진행한다.

 

때문에 현재 숫자에서 backtrack을 진행하냐 마냐를 조건 분기로 나눌 수 있다.

 

backtrack의 과정은 다음과 같다.

1. 먼저 현재 숫자 방문처리를 해준다.

2. 이후 operation_stack에서 pop해주고 이를 op라고 저장한다.(가장 최근에 한 연산이 어떤 연산이었는지 알기 위해)

3. rev_op를 진행한다.

 

이 사실을 유념해두고, 위 그림에서 2번부터 8번까지의 과정을 한 번 봐보자.

 

기본적으로 시작점(1213121)은 좋은 수열이기 때문에 backtrack을 거치지 않는다.

 

그래서 다음 조건을 따지는데, 현재 시작점은 방문처리를 하지 않은 상태이기 때문에 먼저 방문처리를 해주고, 위의 조건 분기에 따라서 op_1을 실행해준다.(여기까지 2번 과정)

 

현재 숫자(12131211)은 나쁜 수열이기 때문에 backtrack을 거쳐야 한다.

 

그래서 위에서 서술한 backtrack의 과정을 거치면, op가 1이 된다.(여기까지 3번 과정)

 

현재 숫자(1213121)은 좋은 수열이기 때문에 backtrack을 거치지 않는다.

하지만 이미 방문된 곳이기 때문에, 가장 최근에 뭐 때문에 backtrack을 했는지 따져줘야 한다.

 

op = 1이므로, op_1을 한번 거쳐서 backtrack을 했다는 사실을 알 수 있다. 때문에, operation_stack에 op_2를 진행한다는 정보를 저장하고, op_2를 진행한다.(여기까지 4번 과정)

 

현재 숫자(12131212)는 나쁜 수열이기 때문에 backtrack을 거쳐야 한다.

위에서 서술한 backtrack의 과정을 거치면, op가 2가 된다.(여기까지 5번 과정)

 

현재 숫자(1213121)은 좋은 수열이기 때문에 backtrack을 거치지 않는다.

하지만 이미 방문된 곳이기 때문에, 가장 최근에 뭐 때문에 backtrack을 했는지 따져줘야 한다.

 

op = 2이므로, operation_stack에 op_3을 진행한다는 정보를 저장하고, op_3을 진행한다.(여기까지 6번 과정)

 

현재 숫자(12131213)는 나쁜 수열이기 때문에 backtrack을 거친다.

위에서 서술한 backtrack의 과정을 거치면, op가 3이 된다.(여기까지 7번 과정)

 

현재 숫자(1213121)는 좋은 수열이기 때문에 backtrack을 거치지 않는다.(원래라면)

하지만, 우리는 더 이상 방문할 곳이 없다는 사실을 잘 안다.(op = 3이기 때문에)

 

그래서 backtrack을 해야 하는데, backtrack의 과정 중에서 1번만 제외하고(이미 방문처리가 된 곳이므로) 2번과 3번 과정만 거치면 된다.(이것이 8번 과정)

 

이 과정을 참고하여, 최종적으로 나오는 수열이 좋은 수열이고, 길이가 N이 되는 것을 만족을 할 때까지 반복을 하면 된다.

 

이를 그대로 코드로 구현하자면 다음과 같다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2661번 좋은수열
# 그리디, 시뮬레이션, 구현, 백트래킹
def is_good(string):
    k = len(string)//2
    for sub_string_len in range(1, k+1):
        s = len(string) - sub_string_len*2 + 1
        for i in range(s):
            if string[i:i+sub_string_len] == string[i+sub_string_len:i+2*sub_string_len]:
                return False
    return True

def op_1(n):
    return 10*n + 1
def op_2(n):
    return 10*n + 2
def op_3(n):
    return 10*n + 3
def rev_op(n):
    return n//10

total = 1
operation_stack = []
check_set = set()
N = int(input())
while True:
    if len(str(total)) == N and is_good(str(total)):
        print(total)
        break
    else:
        if not is_good(str(total)):
            check_set.add(total)
            op = operation_stack.pop()
            total = rev_op(total)
        else:
            if total in check_set:
                if op == 1:
                    operation_stack.append(2)
                    total = op_2(total)
                elif op == 2:
                    operation_stack.append(3)
                    total = op_3(total)
                else:
                    op = operation_stack.pop()
                    total = rev_op(total)
            else:
                check_set.add(total)
                operation_stack.append(1)
                total = op_1(total)