(BOJ)기초(브루트포스)(11) 좋은수열 (2661)

작성일 | In

좋은수열

11. 좋은 수열

  • 숫자 1,2,3으로만 이루어진 수열이 있다.

  • 임의이 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

  • 길이가 N인 좋은 수열들을 N자리의 정수로 보아 그 중 작은 수를 나타내는 수열 구하기

좋은 수열 판단 규칙을 어떻게 정할 것인가? 우선 길이가 N일 때, 123을 만들 수 있는 수열을 출력해보자. 그 뒤, 좋은 수열 판단 알고리즘을 적용해서 체킹해준다.

  • 좋은 수열 판단 알고리즘
  • 1,2,3을 차례대로 넣어가면서
  • 13123123이라는 수가 있다면 먼저 1을 넣는다
  • 131231231을 넣어서, 3과 1 검사, 이후 두글자씩 12와 31 검사
  • 이후 3글자 검사를 해준다.
  • 이를 재귀로 result에 값을 넣을 때마다 반복해준다.

좋은 수열 판단 알고리즘

for i in range(1, len(s)//2+1):
    if s[-i*2:-i] == s[-i:]:
        print(True)

전체코드

def check(s):
    for i in range(1, len(s)//2+1):
        if s[-i*2:-i] == s[-i:]:
            return False
    return True


def DFS(s):
    global result, stop
    if stop:
        return

    if len(result) == N:
        print(result)
        stop = True
        return

    for i in range(1, 4):
        result += str(i)
        if check(result):
            DFS(i)
        result = result[:-1]


N = int(input())
result = ""
stop = False
DFS(0)
  • 좋은 수열 판단 알고리즘을 짜는데 있어서, 별찍기가 큰 도움이 되었다.

참고자료

코드플러스 참고블로그 좋은수열판단알고리즘

0%