https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
www.acmicpc.net
주어진 N개의 숫자의 위치는 변하지 않고 숫자 사이의 연산자의 위치만 바꿔서 계산 결과의 최솟값과 최댓값을 출력하는 문제이다.
solve함수에서 index번째에서 사용할 수 있는 연산자를 사용하는 모든 경우를 구해준다.
연산자를 선택할 때마다 해당 연산자를 사용해서 계산한 값을 넘겨준다.
사용한 연산자는 처음 입력받은 사용할 수 있는 개수에서 -1을 해주고 탐색에서 돌아온 경우 다시 +1을 해준다.
이 부분을 안 해줘서 계속 최솟값과 최댓값이 같은 값으로 나왔었다...
N-1 개의 모든 연산자를 결정해준 경우 최종 계산된 값을 ans 벡터에 추가해준다.
마지막으로 ans 벡터를 정렬해주면 맨 앞에 위치한 값이 최솟값이고 맨 마지막에 위치한 값이 최댓값이 된다.
|
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<int> num;
vector<int> ans;
void solve(int index, int op[], int result) {
//모든 연산자를 선택해준 경우
if(index == n-1) {
//계산 결과를 ans 벡터에 넣어준다.
ans.push_back(result);
return;
}
for(int i=0; i<4; i++) {
//사용할 수 있는 i번째 연산자가 없는 경우
if(op[i] == 0) continue;
//연산자를 사용한다.
op[i] -= 1;
//각각 덧셈인 경우, 뺄셈인 경우, 곱셈인 경우, 나눗셈인 경우에 대해서 결과를 계산해서 넘겨준다.
if(i == 0) {
solve(index+1,op, result+num[index+1]);
} else if(i == 1) {
solve(index+1,op, result-num[index+1]);
} else if(i == 2) {
solve(index+1,op, result*num[index+1]);
} else {
solve(index+1,op, result/num[index+1]);
}
//i번째 연산자를 사용하는 경우를 위에서 보내줬으므로
//다시 돌아왔을때 연산자의 상태를 원래대로 돌려준다.
op[i] += 1;
}
}
int main() {
cin >> n;
int op[4];
//피연산자를 입력
for(int i=0; i<n; i++) {
int x;
cin >> x;
num.push_back(x);
}
//각 연산자의 개수를 입력
for(int i=0; i<4; i++) {
int x;
cin >> x;
op[i] = x;
}
solve(0,op, num[0]);
//계산 결과를 정렬해준다.
sort(ans.begin(), ans.end());
//맨뒤의 값이 최댓값, 맨 앞의 값이 최소값이므로 각각 출력해준다.
cout << ans.front();
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 4963. 섬의 개수 (0) | 2019.06.25 |
|---|---|
| [BOJ] 2667. 단지번호붙이기 (0) | 2019.06.25 |
| [BOJ] 6603. 로또 (0) | 2019.06.20 |
| [BOJ] 10971. 외판원 순회2 (DFS 풀이) (0) | 2019.06.20 |
| [BOJ] 10971. 외판원 순회2 (0) | 2019.06.20 |