Python3
문제
키워드
- 백트래킹
문제 풀이
문제 요구사항
n개의 정수가 순서대로 주어질 때, n−1개의 연산자를 정수 사이에 하나씩 배치한다.
주어진 정수의 순서를 바꿀 수 없으며, 연산자는 덧셈, 뺄셈, 곰셈 이렇게 세 가지 종류가 있다.
연산자 간의 우선 순위를 무시하고 앞에서부터 차례대로 연산한다고 하였을 때, 가능한 식의 최솟값과 최댓값을 출력하는 프로그램.
변수 및 함수 설명
- n: n개의 정수
2≤n≤11 - num: 주어지는 정수 (피연산자)
1≤ 입력으로 주어지는 숫자 ≤100 - plus, sub, multi: 사용 가능한 덧셈, 뺄셈, 곱셈의 개수
(단, 사용 가능한 모든 연산자 개수의 합은 n−1입니다.) - MIN, MAX: 최솟값, 최댓값
- dfs(depth, total, plus, sub, multi): 식을 계산하는 함수
풀이
(입력 및 선언)
- n개의 정수를 입력받고, num에 리스트로 저장한다.
- 사용 가능한 연산자의 개수를 plus, sub, multi 변수에 저장한다.
- MIN, MAX를 최솟값과 최댓값으로 초기화한다.
- dfs 함수를 호출한다.
이때 깊이는 1, 최종값은 num 배열의 첫 번째 원소, 연산자의 개수를 인자로 전달한다.
(식 계산하기)
- 만약 깊이가 n까지 도달했다면, 최솟값과 최댓값을 total과 MIN, MAX 값과 비교해서 더 작고/큰 값을 저장한다.
- 만약 plus에 값이 있으면 재귀 호출을 한다.
이때 깊이는 1 더해서 들어가고, total 값에 num[depth] 값을 더하고, plus 개수는 1 감소시켜 호출한다. - 만약 sub에 값이 있으면 재귀 호출한다.
이때 깊이는 1 증가하고, total - num[depth], sub를 1 감소시킨다. - multi에 값이 있으면 재귀 호출한다.
이때 깊이는 1 증가하고, total * num[depth], multi를 1 감소시킨다.
(최종 출력)
- MIN, MAX 값을 출력한다.
최종 코드
# 계산하기
def dfs(depth, total, plus, sub, multi):
global MIN, MAX
if depth == n:
MIN = min(MIN, total)
MAX = max(MAX, total)
if plus:
dfs(depth + 1, total + num[depth], plus - 1, sub, multi)
if sub:
dfs(depth + 1, total - num[depth], plus, sub - 1, multi)
if multi:
dfs(depth + 1, total * num[depth], plus, sub, multi - 1)
n = int(input())
num = list(map(int, input().split()))
plus, sub, multi = map(int, input().split())
MIN, MAX = float("INF"), -float("INF")
dfs(1, num[0], plus, sub, multi)
print(MIN, MAX)피드백
I mean