https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 부호에 해당하는 리스트를 따로 만든 후 해당 리스트에서 보호의 순사가 바뀜에 따라 값도 바뀌게 되므로 순서가 중요한 순열로 뽑아야 합니다. 따라서 숫자의 경우 num이라는 리스트를 만들어 넣어주고 부호의 경우 따로 x라는 리스트를 만든 후 permutations를 통해 숫자보다 하나 적게 뽑은 후 ( 3 + 3처럼 부호의 경우 숫자보다 하나 적어야 함) 교차하여 부호와 숫자가 모두 포함이 된 리스트를 만든 후 이를 계산하는 calc함수를 구현하면 쉽게 해결할 수 있습니다.
문제 해결을 위한 팁
저의 경우 isdigit()를 통해서 부호와 숫자를 합쳐진 리스트에서 구별했는데 이때 int형애는 isdigit()을 사용할 수 없기 때문에 str을 이용하여 우선 다 문자 형태로 바꿔준 후에 isdigit()을 이용하였습니다.
소스코드
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
from itertools import permutations
def calc(arr):
prev = int(arr[0])
for i in range(1, len(arr)-1):
if arr[i].isdigit() == False:
if arr[i] == '+':
prev += int(arr[i+1])
elif arr[i] == '-':
prev -= int(arr[i+1])
elif arr[i] == '//':
if prev >= 0:
prev = prev // int(arr[i+1])
else:
prev *= -1
prev = prev // int(arr[i+1])
prev *= -1
elif arr[i] == '*':
prev *= int(arr[i+1])
return prev
N = int(input())
num = list(map(int, input().split()))
numOfA, numOfB, numOfC, numOfD = map(int, input().split())
x = []
while True:
if numOfA > 0:
x.append('+')
numOfA -= 1
if numOfB > 0:
x.append('-')
numOfB -= 1
if numOfC > 0:
x.append('*')
numOfC -= 1
if numOfD > 0:
x.append('//')
numOfD -= 1
if numOfA == 0 and numOfB == 0 and numOfC == 0 and numOfD == 0:
break
maximum = int(1e9)*-1
minimum = int(1e9)
for xx in list(permutations(x, N-1)):
j = 0
arr = []
for i in range(N-1):
arr.append(str(num[i]))
arr.append(str(xx[j]))
j += 1
arr.append(str(num[-1]))
result = calc(arr)
maximum = max(maximum, result)
minimum = min(minimum, result)
print(maximum)
print(minimum)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 16234: 인구이동(Python) (0) | 2020.12.07 |
|---|---|
| 백준 알고리즘 18428: 감시 피하기(Python) (0) | 2020.12.05 |
| 백준 알고리즘 18405: 경쟁적 전염(Python) (0) | 2020.12.05 |
| 백준 알고리즘 14502: 연구소(Python) (0) | 2020.12.05 |
| 백준 알고리즘 18352: 특정 거리의 도시 찾기(Python) (0) | 2020.12.04 |