티스토리 뷰

https://www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, ��

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from copy import deepcopy
 
= int(input())
arr = list(map(int, input().split()))
operators = list(map(int, input().split()))
answer = [-int(1e9), int(1e9)]
 
 
def dfs(operand, used, index):
    if index == n:
        if operand > answer[0]:
            answer[0= operand
        if operand < answer[1]:
            answer[1= operand
        return
 
    for i in range(4):
        if used[i] < operators[i]:
            tmp_used = deepcopy(used)
            tmp_used[i] += 1
            if i == 0:
                dfs(operand + arr[index], tmp_used, index + 1)
            elif i == 1:
                dfs(operand - arr[index], tmp_used, index + 1)
            elif i == 2:
                dfs(operand * arr[index], tmp_used, index + 1)
            else:
                num = abs(operand) // arr[index]
                if operand < 0:
                    num *= -1
                dfs(num, tmp_used, index + 1)
 
 
dfs(arr[0], [0000], 1)
print(answer[0])
print(answer[1])
cs

전형적인 dfs문제.

연산자를 몇 번이나 사용했는지 저장하는 리스트를 사용하면서, 사용 횟수를 넘지 않도록 한다.

주의할 점은, 음수를 나누는 연산을 할 때, 문제의 설명에 따라 잘 해야 한다는 것.

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함