링크 : https://www.acmicpc.net/problem/2661
문제 :
아이디어 : N-Queen이랑 비슷해보인다
입력 길이만 주고 → 결과를 리턴
제한조건(동일한 숫자가 연속해서 나타나면 x ) 를 보고 → 백트래킹해서 가지치면서 진행해야겠다
까지생각했음
DFS를 써야겠다
BFS로 하면 안될거라고 생각했던게, 애초에 백트래킹할때 DFS로밖에 못한것도있고, 메모리제한이 128메가라서 1, 2, 3 순서대로 재귀 진행하면, 길이가 n 인상태에서 리턴되는 제일빠른 숫자가 정답 이라고 생각했다
망한코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input().strip())
words = ['1', '2', '3']
def dfs(x) :
global x
#종료조건
if len(x) == N :
print("here is x " + str(x))
return x
#덧셈조건
for word in words :
temp = x + word
i = 1
while i<= len(temp)//2 :
if temp[-2*i:-i] == temp[-i:] :
print(temp, temp[-2*i:-i] , temp[-i:])
return
i+=1
dfs(temp)
start = ""
print(dfs(""))
DFS를 잘못써서 개같이 멸망
1인 상태에서는 ‘11’, ‘12’, ‘13’, 을 확인해야하고, ‘11’은 연속된 숫자이기때문에 1 → 11 → 12 로 확인해야하는데
실제로 해보니 1→ 11 → 2로 움직여서, 이부분을 못해결해서 답지를 봤다
정답코드
def back_tracking(idx):
#1
for i in range(1,(idx//2) +1):
if s[-i:] == s[-2 * i:-i]: return -1
#2
if idx == n:
for i in range(n):
print(s[i], end='')
return 0
#3
for i in range(1, 4):
s.append(i)
if back_tracking(idx + 1) == 0:
return 0
s.pop()
if __name__ == "__main__":
n = int(input())
s = []
back_tracking(0)
#1에서는 재귀조건(연속된 숫자가 나오는지 를 확인하고)
#2에서는 길이(idx) 가 n 일때 진행하는 종료조건을 확인하는거고
#3에서는 for i in [1,2,3]
으로 하나씩 넣어가면서 백트래킹을 진행한다.
리스트s 는 ‘현재 백트래킹중인 숫자가 담겨져있는 리스트’ 이다.
if back_tracking(idx+1) == 0 :
만약 한칸이 늘어났는데, 0이 리턴됐다라는것은
실제로 0이 리턴되는구간은 #2의 리턴값밖에 없기때문에, 이는 ‘어쨋든 길이가 끝까지 갔구나' 라는것을 의미한다.
그게 아니라면, 리턴값이 -1이라서 #3에서 pop()
한다음 다른값이 들어가는 방식으로 구현됐다
'CodingTest' 카테고리의 다른 글
백준 2638 치즈 (0) | 2022.08.17 |
---|---|
백준 20444 색종이와 가위 (0) | 2022.08.17 |
프로그래머스 보석쇼핑 67258 파이썬 (0) | 2022.07.20 |
백준 18232 텔레포트정거장 파이썬 (0) | 2022.07.20 |
백준 10826 피보나치수4 파이썬 (0) | 2022.07.20 |