14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
www.acmicpc.net
배열의 앞에있는 원소를 제거하고 새로운 원소를 배열의 맨 앞에 추가하기 위해 자료구조로 deque를 사용했다.
알고리즘은 간단하다. 앞에 두 원소에 대해 덧셈, 뺄셈, 곱셈, 연산을 수행한다음, 배열에서 앞에 두 원소를 빼내고 연산의 결과값을 배열 맨 앞에 추가한다.
ex) 1 2 3 4 5 -> 1+2=3 -> '3' 3 4 5-> 반복
원소 두개를 빼고 한개를 추가하기 때문에 작업이 이루어질때마다 배열의 원소 갯수는 한개씩 줄어들게 되고,
배열에 원소 갯수가 한개만 남게되면 모든 연산을 다 마쳤다는 뜻이므로 그 결과를 최댓값, 최솟값과 비교하여 저장한다. 그리고 이러한 작업을 4개 연산자로 할 수 있는 모든 경우의 수만큼 반복한다음 최댓값 최솟값을 출력해주면 원하는 답을 얻을 수 있다.
|
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
deque<int> expr;
vector<int> oprt; // oprt[0]: +, oprt[1]: -, oprt[2]: *, oprt[3]: /
const int MAX = -987654321;
const int MIN = 987654321;
int maximum = MAX;
int minimum = MIN;
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
int _operator(int type)
{
int res;
switch (type)
{
case 0:
res = expr[0] + expr[1];
break;
case 1:
res = expr[0] - expr[1];
break;
case 2:
res = expr[0] * expr[1];
break;
case 3:
res = expr[0] / expr[1];
break;
}
return res;
}
void Solution(deque<int>& expr, vector<int>& oprt)
{
int len = expr.size();
if (len == 1) // 기저사례. expr에 원소가 한개라면 결과 출력
{
int result = expr[0];
maximum = max(maximum, result);
minimum = min(minimum, result);
return;
}
for (int i = 0; i < 4; i++)
{
if (oprt[i] == 0) continue;
oprt[i]--;
int res = _operator(i);
int expr0 = expr[0], expr1 = expr[1];
expr.pop_front();
expr.pop_front();
expr.push_front(res);
Solution(expr, oprt);
expr.pop_front();
expr.push_front(expr1);
expr.push_front(expr0);
oprt[i]++;
}
}
int main(void)
{
int num;
cin >> num;
for (int i = 0; i < num; i++)
{
int n;
cin >> n;
expr.push_back(n);
}
for (int i = 0; i < 4; i++)
{
int n;
cin >> n;
oprt.push_back(n);
}
Solution(expr, oprt);
cout << maximum << endl;
cout << minimum << endl;
expr.clear();
oprt.clear();
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 7day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1182번: 부분수열의 합 (0) | 2020.04.13 |
|---|---|
| 백준 1966번: 프린터 큐 (0) | 2020.04.13 |
| 백준 6603번: 로또 (0) | 2020.04.12 |
| 백준 7568번: 덩치 (0) | 2020.04.11 |
| 백준 14502번: 연구소 (0) | 2020.04.11 |