[BOJ 2661] 좋은수열(Python)

문제

좋은수열

---

문제 해설

문제를 이해하기는 쉽지만 어떻게 적용해야할지 난감한 문제였습니다.
n = 8일때, 12131231 인것을 보고 백트래킹으로 해결될 문제라고 생각했습니다.

• 문자열에 1,2,3을 순서대로 추가해 봅니다.(가장 작은 좋은수열을 찾기 위함)
• 추가된 문자열이 좋은 수열인지 확인합니다.

크게보면 위 두가지 순서인데, 각각 dfs, n/2의 시간이 걸리는 완전탐색을 활용했습니다. 추가된 문자를 기준으로 n/2 만큼만 조사하면 좋은수열인지 아닌지 판단할 수 있습니다.

---

풀이 코드

n = int(input())

def check(ans):
    for i in range(1, len(ans) // 2 + 1):
        a, b = "".join(ans[len(ans) - 2 * i : len(ans) - i]), "".join(
            ans[len(ans) - i :]
        )
        if a == b:
            return False
    return True


def dfs(depth, ans):
    if depth == n:
        print("".join(ans))
        exit()
    for i in range(1, 4):
        # 1 ~ 3까지 차례대로 넣고 좋은 수열이면 depth올림
        ans += str(i)
        if check(ans):
            dfs(depth + 1, ans)
        ans.pop()


dfs(0, [])