[백준] [백트래킹] 2661. 좋은 수열

2661. 좋은 수열

2661번: 좋은수열

 

• 내 풀이 - fail
  • 답은 나오는데 메모리 초과
  • n자리 수의 전체 조합 구해서 연속해서 같은 부분수열이 있는지 판별하고
  • 없는 경우는 숫자로 만들어서 비교해서 최솟값 구함
• -> n 이 80자리까지 가능하기 때문에 전체 조합이 3^80 이 되어 무조건 터짐

from collections import deque

number = [1, 2, 3]
n = int(input())
queue = deque()


def dfs(tmp, last, cnt):
    global n
    if cnt == n:
        queue.append(tmp[:])
        return

    for num in number:
        if num == last:
            continue
        tmp[cnt] = num
        dfs(tmp, num, cnt+1)
        tmp[cnt] = 0


dfs([0 for _ in range(n)], 0, 0)
answer = int(1e9)

while queue:
    q = queue.popleft()

    flag = 0
    for i in range(0, (n+1)//2):
        for j in range(i+1, (n+1)//2+1):
            if q[i:j+1] == q[j+1:2*(j+1)-i]:
                flag = 1
        if flag == 1:
            break
    else:
        answer = min(answer, int(''.join(map(str, q))))

print(answer)

 
 

• 📍다른사람 풀이
  • 전체 조합을 구하면 안됨
  • 가장 작은 값을 구하는 거니까 dfs를 돌때 1로 시작하기 -> 완료되면 종료
  • 뒤의 수가 추가된다는 건 앞의 수에서 고려할 때 문제가 없었다는 것
  • 뒤의 수가 추가됨으로써 같게 나올 수 있는 값들을 비교해보기
  • ex) 1 2 1 3 1 2 1 인 경우
    • 1 2 1 3 1 (2) (1)
    • 1 2 1 (3 1) (2 1)
    • 1 (2 1 3) (1 2 1) 
    • -> 3가지 비교가 필요 
  • ex) 1 2 1 3 1 2 1 2 (짝수개인경우) -> 4가지 비교가 필요
  • => 즉, n//2 개만큼의 비교가 필요

n = int(input())

def dfs(tmp, length):
    for i in range(1, length//2+1):
        if tmp[-(i*2):-i] == tmp[-i:]:
            return

    if length == n:
        print(tmp)
        exit()

    dfs(tmp+"1", length+1)
    dfs(tmp+"2", length+1)
    dfs(tmp+"3", length+1)


dfs("1", 1)