[C++] 백준 14888 - 연산자 끼워넣기(백트래킹, 브루트포스, 무식하게 풀기)

0. [c++] 백준

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

1. 풀이

1) 숫자와 연산자를 저장한다.

cin과 for문을 통해 입력된 데이터를 저장해준다.

이번 경우에는 2가지 배열에 데이터를 나눠서 숫자와 연산자를 따로 저장해주었다.

2) 모든 경우에 대해 부호를 넣어준다.

이 문제에서 숫자의 위치는 변하지 않고, 부호의 위치만을 변경하도록 조건을 주었다.

이 조건을 만족시켜주며 문제를 해결하면 되었는데, 모든 경우를 계산해도 충분한 속도가 나오는 데이터 양이기 때문에 모든 경우를 계산하도록 설계를 해보았다.

간단히 각 연산의 시행 수를 count해주고, 이 count가 연산자의 개수를 넘지 않은 경우라면, 연산을 추가적으로 시행하도록 하면 되었다.

마지막으로, 모든 연산이 끝난 후에 결과값을 따로 저장해주는 것으로 코드가 마무리되었다.

2. 소스코드

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

#include<iostream>   using namespace std;   int N; int arr[12]; //순서대로 덧셈, 뺄셈, 곱셈, 나눗셈 개수 int oper[4]; int MAX = -1000000007, MIN = 1000000007;   void calc(int iter, int add, int sub, int mul, int div, int ret) {     //모든 연산이 끝난 경우라면, 그 결과가 최댓값, 최솟값을 넘는지 확인해준다.     if (iter == N - 1) {         if (ret > MAX)             MAX = ret;         if (ret < MIN)             MIN = ret;     }     //각 부호의 연산이 남아있다면, 그 연산을 수행해준다.     //이때, 우리는 모든 경우의 수를 따질 것이므로, 4가지 방향으로 전부 연산을 시행한다.     else {         if (add < oper[0]) {             calc(iter + 1, add + 1, sub, mul, div, ret + arr[iter + 1]);         }         if (sub < oper[1]) {             calc(iter + 1, add, sub + 1, mul, div, ret - arr[iter + 1]);         }         if (mul < oper[2]) {             calc(iter + 1, add, sub, mul + 1, div, ret * arr[iter + 1]);         }         if (div < oper[3]) {             calc(iter + 1, add, sub, mul, div + 1, ret / arr[iter + 1]);         }     } }   int main() {     cin >> N;     //입력된 숫자를 저장     for (int i = 0;i < N;i++) {         cin >> arr[i];     }     //부호의 개수 저장     for (int i = 0;i < 4;i++) {         cin >> oper[i];     }       calc(0, 0, 0, 0, 0, arr[0]);       cout << MAX << "\n" << MIN << endl; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!