★Backtracking Advanced I - 3 Solved★

★ 7490 0 만들기 ★

 

import sys
input=sys.stdin.readline

def track(nums,exp,start):
    if start == len(nums)+1:
        res=eval(exp)
        if res == 0:
            ans=[]
            for i in range(len(exp)):
                if i>=1 and exp[i-1].isdigit() and exp[i].isdigit():
                    ans.extend([' ',exp[i]])
                else:
                    ans.append(exp[i])
            print(*ans,sep='')       
    else:
        #needs to be added
        for x in [' ','+','-']:
            if x == ' ':
                exp+=str(start)
                track(nums,exp,start+1)
                exp=exp[:-1]
            elif x == '+':
                exp+='+'#update exp
                exp+=str(start)
                track(nums,exp,start+1)
                exp=exp[:-2]
            else: #'-'
                exp+='-'#update exp
                exp+=str(start)
                track(nums,exp,start+1)
                exp=exp[:-2]


for _ in range(int(input())): #~10
    N=int(input()) #3~9
    nums=[x for x in range(1,N+1)]
    exp='1'
    track(nums,exp,2)
    print()

 

👇 ASCII 순 출력이므로 빈 칸 → + → - 순서로 tracking

① tracking 이전 exp 식 문자열에 숫자 추가하고 +나 -는 기호까지 추가

② tracking 진행 시 주어진 연산 횟수 만큼 다다르면 eval()로 결과가 0이 나올 경우만 exp 출력(이 때 숫자가 서로 붙어 있는 경우만 빈칸 추가)

③ tracking 이후 exp에 추가된 숫자(또는 추가로 기호) slicing으로 자르고 backtracking(tracking 이후도 관리해주어야)

---

★ 1759 암호 만들기 ★

 

import sys
input=sys.stdin.readline

L,C=map(int,input().split())
letters=list(input().split())
letters.sort()
ans=[]

def track(start):
    if len(ans) == L:
        vowels,consonants=0,0
        for x in ans:
            if x in 'aeiou':
                consonants+=1
            else:
                vowels+=1
        if consonants>=1 and vowels>=2:
            print(*ans,sep='')
    else:
        for i in range(start,C):
            ans.append(letters[i])
            track(i+1)
            ans.pop()


track(0)

 

👇 출력 시, 증가순서로만 출력해야 하므로 for문 시작 index가 track()으로 깊이가 깊어질때마다 1씩 증가하게 설정

---

★ 2023 신기한 소수 ★

 

def is_prime(n):
    for x in range(2,int(n**(1/2))+1):
        if n%x==0:
            return False
    return True

def track(ans):
    if len(ans) == N:
        print(''.join(ans))
    else:
        for n2 in ['1','3','5','7','9']:
            next_str = ''.join(ans) + n2
            if is_prime(int(next_str)): #if prime number
                ans.append(n2)
                track(ans)
                ans.pop()

N=int(input())
if N==1:
    print(2,3,5,7,sep='\n')
else:
    for n in ['2','3','5','7']:
        track([n])

 

👇 첫번째 자리부터 차례대로 소수 판정. 이 때 첫번째 자리 소수 2, 3, 5, 7에서 시작 / 이후 숫자를 붙일 때 자리수 2 이상의 소수는 홀수 내에만 있으므로 1, 3, 5, 7, 9에만돌려 소수판정이 맞다면 tracking 진행 / 기존 백트래킹에서 소수판정 조건만 추가된 유형

---