AlgorithmBOJ

백준 연산자끼워넣기 14888

, , ,

1. 연산자끼워넣기14888

2. 컴퓨팅 스킬

next_permutation

  • 값을 저장 시킬 vector v;
  • 연산자의 개수를 1,2,3,4 의 값으로 넣을 vector cal;
  • #include헤더에 minmax_element으로 최대값과 최소값 구해줍니다.

DFS

  • 재귀호출로 백트래킹으로 구해줍니다.

3. 컴퓨팅 사고

next_permutation

  • n을 입력받아 수를 v에 입력을 받아줍니다.
  • +, -, *, /의 개수를 확인해서 cal 변수에 1,2,3,4를 나누어서 넣어줍니다. 예를 들면, 2 0 1 0 일경우 +의 개수는 2개이므로 1을 두번넣어주고, *의 개수는 1개이므로 3을 한번넣어주고 해당 cal 벡터에는 [1, 1, 3]이 됩니다.
  • cal에 담긴 벡터를 next_permutation을 돌려주면서 순열값 모든경우의 수를 구해줍니다.
  • cal값이 1일 경우 + , 2일경우 -, 3일 경우 *, 4일 경우 / 의 연산대로 조건을 처리해줍니다.
  • 이때, sum = v[0]을 해준이유는 순차적으로 계산을 진행해야하므로 가장 맨처음에 존재하는 값을 sum에 담고 시작하였습니다. 연산자의 개수는 수의 N-1개이기때문에 미리 sum에 값을 넣어주었습니다. 예를 들면 10 + 20를 연산해야 한다고 할 경우 sum = 10을 두고 sum + 20으로 연산을 처리하기위해서 입니다.
  • 조건에 보면 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 합니다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.을 해주어야하므로 sum의 값이 음수일 경우 sum = -sum 으로 양수 값을 변경하고, sum = (sum / v[i]) 을 계산해준 후 다시 음수값으로 변경하였습니다. sum이 양수일 경우 sum = (sum / v[i])로 로직대로 처리하였습니다.
  • minmax_element를 사용하여 max, min값을 동시에 구하였습니다. auto p = minmax_element(ans.begin(), ans.end());의 형식으로 최대값과 최소값을 모두 구할 수 있습니다. *p.second는 최소값, *p.first는 최대값입니다.

4. 해당 +,-,*,/ 연산자에 가중치를 부여하여 그 값에 따라 순열을 통해 모든경우의 수를 구하는것이 키 포인트였습니다.

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보다 클 경우에는 계속해서 재귀호출을 합니다.
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;

4.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
#include <iostream>
#include <vector>
#include <algorihtm>
using namespace std;
vector<int> res;

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

4.2. next_permutation 풀이

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
72
73
74

//
//  08_백준_연산자끼워넣기_14888.cpp
//  algorithm-level-up
//
//  Created by kgh on 02/12/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

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

using namespace std;
int main(void){
    
    int n=0;
    cin >> n;
    vector<int> v(n);
    vector<int> cal;
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    
    for(int i=0; i<4; i++){
        int a = 0;
        cin >> a;
        
        for(int j=0; j<a; j++){
            if(i == 0){
                cal.push_back(1);
            }else if(i == 1){
                cal.push_back(2);
            }else if(i == 2){
                cal.push_back(3);
            }else if(i == 3){
                cal.push_back(4);
            }
        }
    }
    vector<int> ans;
    do{
        int sum = v[0];
        
        for(int i=1; i<v.size(); i++){
            if(cal[i-1] == 1){
                sum = sum + v[i];
            }else if(cal[i-1] == 2){
                sum = sum - v[i];
            }else if(cal[i-1] == 3){
                sum = sum * v[i];
            }else {
                if(sum < 0){
                    sum = -sum;
                    sum = (sum / v[i]);
                    sum = -sum;
                }else {
                    sum = (sum / v[i]);
                }
            }
        }
        ans.push_back(sum);
    }while(next_permutation(cal.begin(), cal.end()));
    
    auto p = minmax_element(ans.begin(), ans.end());
    
    cout << *p.second << '\n';
    cout << *p.first << '\n';
    
    return 0;
}



Share