문제
•
1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.
•
그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.
•
N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.
풀이
•
기본 알고리즘
#Loop
1. ' ' '+' '-' 의 모든 경우의 수를 만든다.
2. 연산한 후 0이 되는지 확인
Python
복사
•
dfs 함수 (모든 경우의 수를 만드는 함수)
- cnt = 사용된 숫자의 개수
- str = 만들어진 문자열 List ex ) [1, '+', 2, '-',,,,]
def dfs(cnt, str):
if cnt == N:
arr.append(str) #모든 숫자가 사용되었으면 후보군 array에 넣기
return
dfs(cnt + 1, str + [' '] + [cnt + 1]) # 모든 케이스에 대해 문자열 만들기 진행
dfs(cnt + 1, str + ['+'] + [cnt + 1])
dfs(cnt + 1, str + ['-'] + [cnt + 1])
Python
복사
•
Main 동작
•
모든 후보군 문자열에 대해 계산하여 0이 되면 출력
arr = list() # 후보군 문자열들이 들어갈 List
N = 0
T = int(input())
for _ in range(T):
arr.clear() #테스트케이스마다 후보군 List 초기화
N = int(input())
temp = list()
temp.append(1) # 맨 앞에 1은 고정이므로
dfs(1, temp)
for i in range(len(arr)):
xx = ''.join(str(e) for e in arr[i]) # List를 문자열로 합쳐줌
if eval(xx.replace(' ','')) == 0: #eval 함수를 통해 문자열을 계산
print(xx)
print()
Python
복사
중요
1.
join은 List 안의 값들이 str인 경우에만 join 가능하다. int가 섞여있다면 아래와 같이 변환!
''.join(str(e) for e in arr[i])
Python
복사
2. eval 함수는 문자열식을 편하게 계산할 수 있다. 꼭 기억해두자
result = eval((2+5)*3)
result # 21
Python
복사
