728x90
반응형
1. 문제
https://www.acmicpc.net/problem/14888
2. 풀이과정
문제 제목처럼 수들 사이에 연산자를 끼워넣어서 계산해보며 최댓값, 최솟값을 갱신해주면 된다.
주어진 연산자들을 나열할 수 있는 모든 경우의 수에 대해 식의 값을 계산해보면 된다.
[코드설명]
opers 는 연산자들을 저장하는 벡터이다.
덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수가
2 1 1 1로 주어졌다면 opers는 아래와 같다.
opers = { '+', '+', '-', '*', '/' }
dfs함수는 opers의 연산자들을 나열할 수 있는 모든 경우의 수를 생성해준다.
위의 opers를 예로 들면 아래와 같다.
+ + - * /
+ + - / *
+ + / - *
.
.
.
calculate함수는 나열된 연산자들을 이용해 앞에서부터 계산한 식의 값을 반환해준다.
문제에서 유의할 점은 계산되는 식의 결과가 항상 -10억보다 크거나 같고, 10억보다 작거나 같으므로
초기 최댓값, 최솟값을 잘 설정해줘야한다.
3. 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> A;
vector<char> opers;
bool visited[11];
int min_v = 1000000000, max_v = -1000000000;
int calculate(vector<char>& o) {
int ret = A[0];
for(int i=1; i<n; i++) {
if(o[i-1] == '+') ret += A[i];
if(o[i-1] == '-') ret -= A[i];
if(o[i-1] == '*') ret *= A[i];
if(o[i-1] == '/') ret /= A[i];
}
return ret;
}
void dfs(vector<char>& v, int depth) {
if(depth == n-1) {
int result = calculate(v);
max_v = max(max_v, result);
min_v = min(min_v, result);
return;
}
for(int i=0; i<n-1; i++) {
if(!visited[i]) {
visited[i] = true;
v.push_back(opers[i]);
dfs(v, depth+1);
visited[i] = false;
v.pop_back();
}
}
}
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
cin >> n;
for(int i=0; i<n; i++) {
int tmp;
cin >> tmp;
A.push_back(tmp);
}
for(int i=0; i<4; i++) {
int tmp;
cin >> tmp;
if(i==0) for(int j=0; j<tmp; j++) opers.push_back('+');
if(i==1) for(int j=0; j<tmp; j++) opers.push_back('-');
if(i==2) for(int j=0; j<tmp; j++) opers.push_back('*');
if(i==3) for(int j=0; j<tmp; j++) opers.push_back('/');
}
vector<char> v;
dfs(v, 0);
cout << max_v << "\n" << min_v;
return 0;
}
728x90
반응형
'💡 Problem Solving > Baekjoon' 카테고리의 다른 글
[백준 - 14502] 연구소 [C++] (0) | 2021.01.16 |
---|---|
[백준 - 14889] 스타트와 링크 [C++] (0) | 2021.01.15 |
[백준 - 10819] 차이를 최대로 [c++] (0) | 2021.01.14 |
[백준 - 11724] 연결 요소의 개수 [C++] (1) | 2020.04.20 |
[백준 - 11403] 경로찾기 [C++] (1) | 2020.04.20 |