백준/완전 탐색

[백준 14888번 / C++] 연산자 끼워넣기

배발자 2022. 3. 17.

목차

    반응형

    완전탐색으로 dfs를 활용해서 풀면된다. 

     

    +, -, * , /  연산자를 차례대로 넣어보는 것이다. 

     

    예를 들어, 

    1 3 5 라는 숫자가 주어졌고 각 연산자를 하나씩 대입해보자. 

     

    1 + 3  = 4

    1 - 3   = -2

    1 * 3  = 3

    1 / 3  = 0 

     

    그리고 연산값이 4부터 다시 dfs를 호출해서 연산하면 된다. 

     

    4 + 5 = 9

    4 - 5 = -1

    4 * 3 = 12

    4 / 5  = 0

     

    이후에 연산값이 -2 부터 다시 dfs 를 호출해서 연산한다. 

     

    이렇게 dfs를 활용해서 완전탐색으로 풀면된다. 

    
      
    #include <queue>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define INF 987654321;
    bool check[123456 * 2+1];
    vector <int> v;
    int result_max = -INF;
    int result_min = INF;
    int level;
    void dfs(int plus, int minus, int multi, int divide, int result, int cnt) {
    if (plus < 0 || minus < 0 || multi < 0 || divide < 0)return;
    if (cnt == v.size()) {
    result_max = max(result, result_max);
    result_min = min(result, result_min);
    return;
    }
    dfs(plus - 1, minus, multi, divide, result + v[cnt], cnt+1);
    dfs(plus , minus-1, multi, divide, result - v[cnt], cnt+1);
    dfs(plus , minus, multi-1, divide, result * v[cnt], cnt+1);
    dfs(plus , minus, multi, divide-1, result / v[cnt], cnt+1);
    }
    int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
    int a; cin >> a;
    v.push_back(a);
    }
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    dfs(a,b,c,d, v[0], 1);
    cout << result_max << endl;
    cout << result_min << endl;
    }
     

    14888번: 연산자 끼워넣기

    첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, ...

    www.acmicpc.net

    [백준 14888번 / C++] 연산자 끼워넣기

    반응형

    '백준 > 완전 탐색' 카테고리의 다른 글

    [백준 1963번 / C++] 소수 경로  (0) 2022.03.25
    [백준 15649번 / C++] N과 M (1)  (0) 2022.03.24
    [백준 2529번 / C++] 부등호  (0) 2022.02.19
    [백준 1107번 / C++] 리모컨  (0) 2022.02.14
    [백준 14502번 / C++] 연구소  (0) 2022.01.28

    댓글