[백준] 7490번 - 0만들기

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

 

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

예제 입력 1 

2
3
7

예제 출력 1 

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

---

문제 풀이

 

백트래킹을 사용한 이유

“모든 경우를 만들어봐라”

이 말 나오면  떠올려야 하는 게
-> 완전탐색
-> 그중에서도 백트래킹(DFS )

---

① 선택지가 계속 갈라짐 (트리 구조)

숫자 사이마다 선택 가능:

 

1 _ 2 _ 3 _ 4 ... 

   ↑   ↑   ↑  

  3개 3개 3개

 

각 칸마다 선택지가 존재한다.

 

이건 DP가 아니라 경우 생성 문제.

---

② 중간 결과가 의미 없음

DP는 지금까지 계산한 결과가 나중에도 재사용될 경우 사용한다.

1+2-

1-2+

1 2+

 

이 중간 상태들이 서로 재사용되지 않음.
그냥 끝까지 만들어야 값이 의미 생김.

그래서 DP 아니고 DFS를 사용하는 문제 

---

③ 조건 만족하는 경우 전부 출력

모든	완전탐색
가능한	가지 뻗기
출력	경우 자체가 답

경로 찾기 문제 → DFS/백트래킹

 

 

순서

① 식을 문자열로 만든다 (DFS)

예를 들어 N=4라면

1 ? 2 ? 3 ? 4

 

여기 물음표 자리에 3가지 선택:

+, -,' '

 

② 완성된 식을 계산

1-2 3+4

이런 경우에 바로 계산 못 함

그래서 공백을 제거해줘야한다.

expr = expr.replace(' ','')

 

 계산

if eval(expr) ==0:

 

---

코드 흐름

def dfs(num, expr):
if num == N:
# 마지막 숫자까지 만들었으면 계산
if evaluate(expr) ==0:
            result.append(expr)
return

    next_num = num +1

    dfs(next_num, expr +"+" +str(next_num))
    dfs(next_num, expr +"-" +str(next_num))
    dfs(next_num, expr +" " +str(next_num))

처음 시작:

dfs(1,"1")

---

출력이 ASCII 순서여야 함

ASCII 순서:

' ' <'+' <'-'

그래서 DFS 호출 순서를 이렇게 해야 함:

dfs(  ," " ,  )
dfs(  ,"+" ,  )
dfs(  ,"-" ,  )

 

 

최종 코드

# 공백제거
import sys
input=sys.stdin.readline

def dfs(n,expr):
    # n = 지금까지 사용한 마지막 숫자
    if n==N: # 모든 숫자를 다 사용했을 때
        # 공백 제거 후 계산
        calc_expr=expr.replace(' ','')
        if eval(calc_expr)==0: # 계산해서 0이 나오면
            results.append(expr)
        return 
    # 다음 숫자 추가
    next_num=n+1
    
    # 아스키 순서
    dfs(next_num,expr+' '+str(next_num))
    dfs(next_num,expr+'+'+str(next_num))
    dfs(next_num,expr+'-'+str(next_num))

# 테스트 케이스 수 
T=int(input())

# 각 테스트 케이스 반복
for _ in range(T):
    N=int(input())
    results=[]
    
    dfs(1,'1') # DFS 시작
    
    for res in results:
        print(res)
    print()