-
7490. [Python]0 만들기Python_알고리즘/Gold V 2023. 10. 11. 01:07
1. 문제
https://www.acmicpc.net/problem/7490
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 재귀
- 백트래킹
3. 파이썬 코드
# 연산 결과가 0인 값을 출력할 함수 def calculator(num): global ans # 연산을 진행할 변수 answer = "" # 정답을 출력할 변수 temp = "" # N값과 num이 같으면 if num == N: # 마지막 값을 리스트에 추가 ans.append(str(num)) # ans 값을 순회하며 for i in ans: # 공백인 경우 정답을 출력할 변수에 값을 더해줌 if i == " ": temp += i # 외의 경우 둘다 값 추가 else: answer += i temp += i # 연산한 결과가 0인 경우 temp 출력 if eval(answer) == 0: print(temp) # 백트래킹 ans.pop() return else: # 연산자를 반복하며 재귀와 백트래킹 for i in [" ","+", "-"]: ans.append(str(num)) ans.append(i) calculator(num+1) ans.pop() ans.pop() T = int(input()) for _ in range(T): N = int(input()) ans = [] calculator(1) print()
4. 문제를 풀고난 후 생각
- 아스키 코드의 순서에 맞도록 공백, +, - 순으로 반복문을 돌려가며 공백의 경우 정답을 출력할 문자열과 계산을 할 문자열을 나눠서 저장해준다.
- 계산을 할 문자열을 eval 함수를 사용하여 계산한 결과가 0인 경우 정답을 저장한 문자열을 출력하는 식으로 문제를 풀었다.
- 재귀와 백트래킹을 이용한 문제로 연습해보기 좋았던 문제같다.
5. 문제를 푸는데 도움이 되는 지식
- 백트래킹
'Python_알고리즘 > Gold V' 카테고리의 다른 글
1374. [Python]강의실 (0) 2023.10.30 1245. [Python]농장 관리 (1) 2023.10.21 1759. [Python]암호 만들기 (0) 2023.10.09 1107. [Python]리모컨 (1) 2023.10.02 15686. [Python]치킨 배달 (0) 2023.09.22