전공/백준
2661
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값이 이미 충분히 작았기 때문에 크게 무리는 없었던 것 같다.
- 전형적인 백트래킹 문제인듯 하다.
참고 사이트
-