yha97 2023. 6. 26. 09:25

날짜 : 2023. 06. 26

사용 언어 : python

 

문제

 

 

코드

import sys

def check(s):
    for i in range(1, len(s) // 2 + 1):
        idx = 0
        while idx + 2 * i < len(s) + 1:
            if s[idx:idx+i] == s[idx+i:idx+2*i]: return False  # 좋은수열 x
            idx += 1
    return True

def back(s):
    if len(s) == n:  # 최소한의 좋은수열 -> 곧바로 종료
        print(s)
        exit(0)
    for i in range(1, 4):
        next = s + str(i)  # 붙이고 체크
        if check(next): back(next)


n = int(sys.stdin.readline())
back("")

 

 

풀이

- 비어있는 문자열에 for문을 사용해서 1, 2, 3을 붙이고, 생성된 문자열이 좋은수열인지 체크한다.

- 좋은수열이 아닌경우에는 이후 문자열은 무조건 좋은수열이 아닐 것이기 때문에 pass, 좋은수열인 경우에는 해당 수열(문자열)을 토대로 똑같이 재귀한다.

- 이후 수열의 길이가 n과 동일해지면 값을 출력 후 프로그램을 exit(0)을 사용해 종료한다.

(* 최소값을 출력해야 하기 때문에 1, 2, 3 순서로 붙인 다음 재귀)

 

알게된 점

- 골4라서 쫄았지만 의외로 금방 풀리는 문제였다.

- 해시에 저장해서 방문처리를 해볼까 했는데 n값이 이미 충분히 작았기 때문에 크게 무리는 없었던 것 같다.

- 전형적인 백트래킹 문제인듯 하다.

 

 

참고 사이트