[Python] 백준 2661 - 좋은수열 문제 풀이

Overview

BOJ 2661번 좋은수열 Python 문제 풀이
분류: Backtracking (백트래킹)

---

문제 페이지

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

---

풀이 코드

from sys import stdin
from typing import List


def dfs(seq: List[int], idx: int, n: int) -> str:
    for i in range(1, idx // 2 + 1):
        if seq[-2 * i:-i] == seq[-i:]:
            return ''

    if idx == n:
        return ''.join(map(str, seq))

    for i in range(1, 4):
        res = dfs(seq + [i], idx + 1, n)
        if res:
            return res


def main():
    n = int(stdin.readline())
    print(dfs([], 0, n))


if __name__ == "__main__":
    main()

백트래킹을 통해 작은 숫자 순서대로 숫자를 만들어나간다. 만들어 나가는 도중에 나쁜 수열이 발견되면 재귀를 빠져나와서 그 다음 숫자를 더해나간다.