완전탐색
- 가능한 모든 경우의 수를 탐색하는 유형이다
- 문제의 depth가 크지 않을 때는 재귀로 풀 수 있다
- 재귀로 푸는 문제가 많다
- 재귀의 끝 (탈출조건)에 도달했을 때, 1을 리턴해 경우의 수를 카운트한다, 또는 답을 계산해서 리턴한다 (리턴된 값을 받아 최대/최소를 업데이트 한다)
- 경우의 수, 최대, 최소를 구하는 문제는 완전탐색 유형이다
- 완전탐색을 수행하는 방법은
- for, if 문 활용
- DFS 를 돌리면서 depth마다 상태를 결정 또는 탐색 방향을 결정
- 예를 들어, 상하좌우 방향으로 DFS 재귀 수행
- 예를 들어, 특정 아이템을 선택하는경우, 선택하지 않는 경우 각각 DFS 재귀 수행
- 비트마스크
- 재귀를 돌고 나오면 기존 상태를 복원해야한다
노트
1) 수식을 다루는 방법
- 연산자와 숫자를 분리해 별도의 array에 저장한다
풀이
1) 왼쪽부터 순차적으로 계산하고, 값을 누적해나가는데
2) 현재 값, 연산자를 바로 실행한 후 누적값에 연산하는 경우
3) 현재 값과 그 다음값을 먼저 연산한 후 누적값에 연산하는 경우
4) 위 두가지 경우로 나눌 수 있고, 각각 처리해서 재귀를 돌리면 된다
틀린 이유
1) eval 함수로 풀려고 했는데 안됨 (다시 시도하기)
2) 연산자 문제는 연산자와 숫자를 잘 나누자
3) 문제에서 숫자는 한자리라고 조건이 있었는데, 제대로 안읽음
코드
import sys
def calc(left, op, right):
if op == '+':
return left + right
if op == '-':
return left - right
if op == '*':
return left * right
else:
raise NotImplementedError
def solve(cum_res, idx):
if idx >= len(op_list):
return cum_res
out = -sys.maxsize
# 괄호 연산 없이, 바로 숫자와 연산자를 수행한다
# 앞의 누적된 값에 현재 값을 연산한다
# cum_res + num, cum_res - num ...
cost = calc(cum_res, op_list[idx], num_list[idx+1])
# 위와같이 했을 경우에 대해 다음단계 진행
sub_out = solve(cost, idx+1)
out = max(out, sub_out)
# 뒤에 나오는 숫자, 연산자에 대해 괄호 연산 적용 후
# 기존 누적된 값에, 해당값을 연산한다
# 누적된 값 + (b + c) -> b + c 먼저 연산, a 에 추가 연산
if idx + 1 < len(op_list):
next_cost = calc(num_list[idx+1], op_list[idx+1], num_list[idx+2])
real_cost = calc(cum_res, op_list[idx], next_cost)
sub_out = solve(real_cost, idx+2)
out = max(out, sub_out)
return out
sys.stdin = open('16637.txt')
n = int(input())
seq = input()
op_list = []
num_list = []
# 1 + 3
for s in seq:
if s == '+' or s == '-' or s == '*':
op_list.append(s)
else:
num_list.append(int(s))
out = solve(num_list[0], 0)
print(out)
