2661 좋은수열

💡문제 분석 요약

• 숫자 1, 2, 3으로만 이뤄지는 수열 중에서 좋은 수열을 찾는다.
• 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이다.
• 좋은 수열 중에서 가장 작은 값을 출력한다.

💡알고리즘 설계

• 모든 수열을 나열하고, 인덱스 0부터 끝까지 반복되는 구간이 있는지 확인해보려 했는데, 모든 수열의 경우의 수는 3^80이므로 불가능하다.
• 모든 수열 중, 좋은 수열을 찾고 그 중에서 min을 찾기보다, 처음부터 min에서 시작해서 좋은 수열이라면 출력하는 쪽이 나아보인다.

💡코드

n = int(input())
nums = []

def check(idx):
    for i in range(1, (idx // 2) + 1):
        if nums[-i:] == nums[-2 * i:-i]: # 리스트 s의 마지막 i개 요소와, 그 앞의 i개 요소가 같다면 중복된 부분 수열이 있다는 뜻
            return False
    return True

def back_tracking(idx):
    if idx == n: # 탈출 조건: 수열의 길이가 n에 도달하면 출력하고 종료
        print(*nums, sep='') # 붙여서 출력하려면 sep 써주면 됨
        exit() # 찾았으니 바로 종료

    for i in range(1, 4): # 1, 2, 3에 대해서만 진행
        nums.append(i)
        if check(idx + 1): # 중복 검사를 통과하면 다음 단계로 진행
            back_tracking(idx + 1)
        nums.pop()

back_tracking(0)

💡시간복잡도

• 최악의 경우 O(3^n)이고 n이 80까지 가능하므로 무조건 시간초과이다. 그러나 백트래킹 사용 & 최소의 좋은 수열을 찾으면 바로 종료되므로 실제 동작시간은 이보다 작다.

💡 틀린 이유

• chekc 함수를 잘 못써서 틀렸다. 사실 백트래킹을 실행하는 것보다, 좋은 수열인지 체크하는 게 더 중요했는데 그게 잘 안됐다.

💡 틀린 부분 수정 or 다른 풀이

• "check"를 한다는 맥락은 거의 다 동일했는데, 백트래킹에서 1, 2, 3을 넣는 방법이 신기한 풀이를 하나 소개해본다.

def recursive(num):
    global N, res
    if len(num) == N:
        print(num)
        exit()
    for i in '123':
        if check(num + str(i)):
            recursive(num + str(i))
    return

 

출처 : https://velog.io/@djagmlrhks3/Algorithm-BaekJoon-2661.-%EC%A2%8B%EC%9D%80-%EC%88%98%EC%97%B4-by-Python

[Algorithm] BaekJoon : 2661. 좋은 수열 by Python

 

💡 느낀점 or 기억할정보

• 문제의 조건을 잘 읽어야한다. 그래야 탈출 조건을 쓰고, 시간을 아낄 방법을 찾을 수 있다.