[백준] 2661번: 좋은수열 / Python / 백트래킹
좋은수열
-
문제
숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.다음은 나쁜 수열의 예이다.
33
32121323
123123213다음은 좋은 수열의 예이다.
2
32
32123
1232123길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.
-
입력
입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다. -
출력
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
나의 풀이
- 재귀함수를 이용하자. 재귀함수는 종료조건을 명확히 설정하는 것이 중요!
- 좋은수열인지 아닌지 판단하는 함수는 따로 빼서 정의하였다. 1부터 문자열 길이의 절반 단위까지 범위를 늘려가면서 구간을 비교하면 된다.
def getResult(idx):
global isExit
if isExit: return
if idx >= n:
# 정답 출력
print(''.join(result))
# 첫번째 반환되는 수열이 가장 작으므로 종료하도록 설정
isExit = True
else:
for i in ['1', '2', '3']:
result[idx] = i
# 현재 채워진 인덱스까지 좋은 수열인지 확인, 좋은 수열이면 다음 숫자 찾기
if isGood(result[:idx + 1]):
getResult(idx + 1)
# 좋은 수열인지 판단하는 함수
def isGood(nums):
# 1부터 수열 길이의 절반까지 범위를 늘려가면서 구간 비교
for tkn_size in range(1, len(nums) // 2 + 1):
if nums[-tkn_size:] == nums[-(2 * tkn_size):-tkn_size]:
return False
return True
n = int(input())
result = [0] * n
isExit = False
getResult(0)
Author And Source
이 문제에 관하여([백준] 2661번: 좋은수열 / Python / 백트래킹), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dhelee/일일코테-Day9저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)