AlgorithmBOJ

백준 연산자끼워넣기2 15658

, , ,

연산자끼워넣기(2)15658

1. 컴퓨팅 스킬

DFS

  • 재귀호출로 백트래킹으로 구해줍니다.
  • 연산자끼워넣기 1번문제와 같은 원리입니다. 정답 또한 같습니다.

2. 컴퓨팅 사고

DFS 백트래킹

  • 맨처음 dfs(v,1,v[0],plus,minus,multi,div); 호출할 때 왜 idx = 1로 시작하고, sum의 값을 v[0]의 값을 넘겨주는가에 대한 의문을 갖고 계신분들이 있습니다. idx를 1로 시작한 이유는 곱하기나, 나눗셈의 경우에서 sum의 값이 0일 경우 올바르지 않은 값이 연산되게 됩니다. 따라서, v[0] (+, -, *, /) v[1] 의 형태로 연산이 되게 됩니다. 따라서 올바른 값을 구할 수 있습니다. 곰곰히 생각해보시면 어떤 말씀인지 알 것이라 생각합니다.
  • 입력받은 plus,minus,multi,div의 개수를 0보다 클 경우에는 계속해서 재귀호출을 합니다.
  • 시간복잡도 계산 총 연산자(+,-,*,/) 4개의 연산자이고, 총 N은 (2<=N<=11) 11까지 이므로 4^10 = 1048570의 복잡도를 가지게 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
if(plus > 0){
    dfs(v,idx+1,sum+v[idx],plus-1, minus, multi, div);
}
if(minus > 0){
    dfs(v,idx+1,sum-v[idx], plus, minus-1, multi, div);
}
if(multi > 0){
    dfs(v,idx+1,sum*v[idx], plus, minus, multi-1, div);
}
if(div > 0){
    dfs(v,idx+1,sum/v[idx], plus, minus, multi, div-1);
}
  • 만약 v.size() == idx 모든 원소의 개수를 확인하였을 경우에 현재 sum값을 res 벡터에 값을 넣어줍니다. 그 후 auto p = minmax_element(res.begin(), res.end());를 사용하여 최댓값과 최솟값을 구해주게 됩니다. 이렇게 구하지 않고도 문제의 조건에서보면 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다 라는 조건이 있습니다.
    이러한 것들에 따라 값을 max함수와 min함수를 사용하면서 최댓값과 최솟값을 구해줍니다.
    다른분들의 풀이를 보니 이런식으로 사용하시는것을 보고 배우게 되었습니다.
1
2
3
4
5
6
const int MAX = 1000000000 + 1;
int maxResult = -MAX, minResult = MAX;
 maxResult = max(maxResult, sum);
 minResult = min(minResult, sum);
 cout << maxResult << endl;
 cout << minResult << endl;

2.1. DFS 백트래킹 풀이

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
//
//  12_백준_연산자끼워넣기2_15658.cpp
//  algorithm-level-up
//
//  Created by kgh on 20/12/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;
vector<int> res;

void dfs(vector<int> v, int sum, int idx, int plus, int minus, int multi, int div){
    
    if(idx == v.size()){
        res.push_back(sum);
        return;
    }
    
    if(plus > 0){
        dfs(v,sum+v[idx],idx+1, plus-1,minus,multi,div);
    }
    if(minus > 0){
        dfs(v,sum-v[idx],idx+1, plus,minus-1,multi,div);
    }
    if(multi > 0){
        dfs(v,sum*v[idx],idx+1, plus,minus,multi-1,div);
    }
    if(div > 0){
        dfs(v,sum/v[idx],idx+1, plus,minus,multi,div-1);
    }
    
    
}
int main(void){
    int n;
    cin >> n;
    vector<int> v(n);
    int plus=0;
    int minus=0;
    int multi=0;
    int div=0;
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    
    for(int i=0; i<4; i++){
        int cal=0;
        cin >> cal;
        if(i == 0){
            plus = cal;
        }else if(i == 1){
            minus = cal;
        }else if(i == 2){
            multi = cal;
        }else {
            div = cal;
        }
    }
    
    dfs(v, v[0],1,plus, minus, multi, div);
    auto p = minmax_element(res.begin(), res.end());
    cout << *p.second << " " <<  *p.first;
    
    return 0;
}


Share