문제
https://www.acmicpc.net/problem/7490
7490번: 0 만들기
각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.
www.acmicpc.net
코드
t=int(input())
def cal(temp):
#배열 맨뒤에 붙은 "+", "-". " "제거
temp = temp[:-1]
#정답을 위해 원본 저장
ori=temp
temp=temp.replace(" ","")
#eval함수를 통해 string 수식 계산
if eval(temp)==0:
s.add(ori)
def dfs(index, temp):
if index==len(array):
cal(temp)
return
dfs(index+1,temp+str(array[index])+"+")
dfs(index+1,temp+str(array[index])+"-")
dfs(index+1,temp+str(array[index])+" ")
for _ in range(t):
s=set()
n=int(input())
array=[]
for i in range(n):
array.append(i+1)
dfs(0,"")
#문제 조건인 ASCII 정렬을 위해 list로 변환
result=list(s)
result.sort()
for i in result:
print(i)
print()
시간 복잡도
숫자 사이마다 ("+","-"," ")이 가능하므로 3**n
'문제풀이 > 기타' 카테고리의 다른 글
[파이썬] [슬라이딩] 백준 1522 문자열 교환 (0) | 2023.03.16 |
---|---|
[파이썬] [투포인터] 백준 20922 겹치는 건 싫어 (0) | 2023.02.24 |
[파이썬] [백트래킹] 백준 22251 빌런 호석 (0) | 2023.02.17 |
[파이썬] [스택] 백준 1863 스카이라인 (0) | 2023.02.15 |
[파이썬] [스택] 백준 2493 탑 (0) | 2023.01.27 |