문제링크
✍️ 풀이
주어진 연산 값이 + 는 x개 - 는 y개 같은 형식으로 주어졌다. 이를 어떻게 DFS 백트래킹 형식으로 풀어야 할지 감이 오지 않았다.
나는 일반적인 DFS처럼 만들기 위해 각각의 개수에 대해 배열을 만들어 방문 체크를 할 수 있도록 만들었다.
🛠 나의 코드
def DFS(index, val):
global mx, mn
if index == n-1:
mx = max(mx, val)
mn = min(mn, val)
return
for i in range(len(oper)):
if check[i]:
continue
check[i] = True
if oper[i] == 0:
DFS(index + 1, val + num[index+1])
elif oper[i] == 1:
DFS(index + 1, val - num[index+1])
elif oper[i] == 2:
DFS(index + 1, val * num[index+1])
else:
DFS(index + 1, val//num[index+1] if val > 0 else -((-val)//num[index+1]))
check[i] = False
n = int(input())
num = list(map(int, input().split()))
operator = list(map(int, input().split()))
oper = []
for i in range(len(operator)):
for j in range(operator[i]):
oper.append(i)
check = [False]*len(oper)
mx = int(-1e9)
mn = int(1e9)
sm = num[0]
DFS(0, sm)
print(mx)
print(mn)📝 정리
- 주어진 연산자 형태를 유지하면서 풀기 위해선 연산자 갯수를 인자로 넘겨가며 푸는 방법이 있다. -> 아래의 링크를 참고하자
🎈 참고
Go Go