BOJ: Q2661 - 좋은 수열 [ 골드 4 ]
문제
숫자 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들 사이에는 빈칸을 두지 않는다.
예제
입력
7출력
1213121풀이
처음에는 입력받은 숫자의 길이 만큼의 수를 만들고(111...) 1씩 올려가며 좋은 수열을 찾았는데 시간초과가 났다.
다른 방법을 찾아야 할 것 같아 고민하다 다음과 같은 방법으로 해결하였다.
import sys
# 좋은 수열 / 나쁜 수열 확인 함수
def isGoodArr(arr):
arr_len = len(arr) # 수열 길이
for part_len in range(1, arr_len // 2 + 1): # 비교할 부분수열의 길이
# 부분수열 비교 시작
for part_start in range(part_len, arr_len - part_len + 1):
# 같은 부분수열 발견하면
if arr[part_start - part_len:part_start] == arr[part_start:part_start + part_len]:
return False # False 리턴
else: # 모든 부분수열이 다르면
return True # True 리턴
# 백트래킹
def dfs(arr, depth):
if depth == N: # 원하는 길이가 되면
print("".join(list(map(str, arr)))) # 수열 출력
sys.exit() # 종료
arr.append(1) # 1 추가 (아무 수나 상관 없음)
for i in range(1, 4): # 1부터 3까지 반복
arr.pop()
arr.append(i)
if isGoodArr(arr): # 해당 수열이 좋은 수열이면
if not dfs(arr, depth + 1): # 다음 다리 수 시작
# 만약 다음 자리 수에서 1~3 모두 넣어도 좋은 수열이 없다면 현재 자리수 1 증가
continue
else:
# 현재 자리 수 1~3 모두 넣어도 좋은 수열이 없는 경우
arr.pop() # 이번 자리 수 없앰
return False # False 리턴
N = int(input()) # 입력
dfs([1], 1) # 백트래킹 시작1부터 시작, 숫자 하나씩 붙여가며 좋은 수열인지 판단하는 방법으로 해결했다.
숫자 하나를 붙일 때 마다 좋은 수열인지 판단하면 위에서 말한 모든 자리수를 만든다음 1씩 증가시키며 좋은 수열인지 판단하는 방법보다는 판단하는 수가 적게 된다. 앞자리에서 이미 나쁜 수열이면 뒷자리가 다른 것들을 모두 안해도 되기 때문.
위의 코드로 실행하게 되면 아래와 같은 순서로 판단한다.
1 -> 좋은 수열
11 -> 나쁜 수열 마지막 수 1 증가
12 -> 좋은 수열
121 -> 좋은 수열
1211 -> 나쁜 수열 마지막 수 1 증가
1212 -> 나쁜 수열 마지막 수 1 증가
1213 -> 좋은 수열
12131 -> 좋은 수열
121311 -> 나쁜 수열 마지막 수 1 증가
121312 -> 좋은 수열
1213121 -> 좋은 수열위와 같은 과정이므로 예제의 입력인 7을 입력해도 많이 시도하지 않고 금방 찾게 되고, N의 최댓값인 80을 입력해도 1초 이내에 찾을 수 있게 된다.
