baekjoon 7490: 0 만들기

https://www.acmicpc.net/problem/7490

7490번: 0 만들기

문제해석: 1부터 주어진 숫자까지의 수를 다 연산하여 0이 되는 경우를 만든다!

사용기술: dfs 백트래킹 완전탐색

---

일단 n의 크기가 10이하이니 시간초과에 대한 생각없이 풀이시작

 

문제를 풀고 나서 보니 단순히 while문으로도 구현이 가능할 거 같긴하다.

 

출력값이 테스트케이스마다 띄어쓰기가 있어서 그부분에 주의 해주어야됨! 문제는 많이 어렵지 않지만 출력오류를 겪음

---

 

예를들어 숫자가 3이라면 나같은경우 path라는 배열에 [1, '',2 ,'', 3]  이렇게 배열을 지정해준 뒤 dfs트리에 branch(가지의갯수)를 3개로 지정하고 dfs를 풀이하였다.([+, -, ' '])

t = int(input())
lst = [' ','+','-']
cnt = 0
for tc in range(t):
    n = int(input())
    path = []
    result = []
    for i in range(1,n+1):
        path.append(i)
        path.append('')
    path.pop(-1)
    arr = []
    used = [0]*3
    # tc마다 줄바꿈을 해주기 위한 cnt
    if cnt >=1:
        print()
    cnt=1
    def dfs(level):
        global Sum, arr, result
        if level==2*n-1:

            for i in range(len(path)):
                arr.append(path[i])

            while ' ' in arr:
                a = arr.index(' ')
                arr[a] = int(str(arr[a-1])+str(arr[a+1]))
                arr.pop(a-1)
                arr.pop(a)

            Sum = arr[0]
            for i in range(1,len(arr),2):
                if arr[i] =='+':
                    Sum += arr[i+1]
                if arr[i] =='-':
                    Sum -= arr[i+1]
            if Sum == 0:
                for i in range(len(path)):
                    print(path[i],end='')
                print()
            arr= []
            return

        for i in range(3):
            path[level] = lst[i]
            dfs(level+2)
    dfs(1)