[문제 바로가기] https://www.acmicpc.net/problem/2661
📌문제 설명
숫자 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들 사이에는 빈칸을 두지 않는다.
💡 문제 풀이
같은 길이임에도 좋은 수열은 다양하게 나올 수 있다.
ex) 길이가 3인 좋은 수열은 '121', '123', '212' 등..
하지만 문제에서는 '가장 작은' 좋은 수열을 찾으라고 했으므로 백트래킹을 이용하여 해결해야한다는 것을 파악했다.
1부터 3까지 순서대로 수열 뒤에 붙이면서 좋은 수열인지 확인만 해주면 되는 문제다.
step 1)
문제를 해결하기 위해서 함수를 작성하여 두 부분으로 나누었다.
- 백트래킹을 진행하는 재귀함수 : recursive
- 좋은 수열인지 확인하는 함수 : check
step 2)
먼저 recursive 함수다.
좋은 수열인지 쉽게 파악하기 위해서 수열을 string 타입으로 만들어 진행하였다. → 슬라이싱(인덱스) 사용
가장 작은 좋은 수열을 만들기 위해서는 1, 2, 3 순서대로 수열에 덧붙여 진행하면 되기 때문에 반복문을 이용하여 길이 N의 좋은 수열을 만들었다.
recursive 함수의 종료조건은 수열의 길이가 N일 때 이다.
※ 주의할 점은 '가장 작은 수'의 좋은 수열을 찾는 것이다.
재귀 종료를 return으로 작성한다면 recursive 함수는 N길이의 '좋은 수열'을 계속해서 찾게된다.
따라서, 파이썬에서 프로그램을 종료시키는 exit() 함수를 사용하여 재귀를 종료시켰다.
step 3)
recursive 함수에서 수열을 만들면 해당 수열이 '좋은 수열'인지 확인해야 한다. → check 함수
좋은 수열인지 확인하기 위해서 슬라이싱(인덱스)을 사용했다.
인접한 두 개의 부분 수열 중 가장 긴 경우는 현재 수열의 길이의 N/2이기 때문에 해당 길이까지 인접한 두 수열이 일치하는지 파악한다.
만약 일치한다면 좋은 수열이 아님을 return 한다.(False)
N/2 길이까지 인접한 두 수열이 일치하지 않으면 좋은 수열임을 return 한다.(True)
코드는 다음과 같다.
def check(num):
length = len(num)
for idx in range(1, length//2 + 1):
if num[-idx:] == num[-(idx*2):-idx]:
return False
else:
return True
def recursive(num):
global N, res
if len(num) == N:
print(num)
exit()
for i in '123':
if check(num + str(i)):
recursive(num + str(i))
return
N = int(input())
recursive('1')
