Suhwanc

문제 링크 : https://www.acmicpc.net/problem/15658

 

15658번: 연산자 끼워넣기 (2)

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

www.acmicpc.net

풀이

브루트 포스 문제입니다!

문제 난이도에 비해 생각보다 쉽지 않아서 많이 고전했던 문제이다.

이 문제는 개인적으로는 그 전 시리즈 문제 (BOJ 14888번 연산자 끼워넣기 https://www.acmicpc.net/problem/14888

보다 어렵다고 생각했는데 아마 브루트 포스에 익숙치 않아서 그런것 같다.

이 문제도 일반적인 bfs처럼 가지치기가 필요한데 최소경로로 하는 것이 아니기 때문에 모든 경우를 다 해보는 브루트 포스를 이용하고자 한다.

이 문제에서 연산의 경우의 수는 총 4가지이며 각각 '+','-','*','/' 이다.

(참고로, 연산의 가짓수가 최대 44개까지 존재하므로 수열을 통해 이 문제를 해결할 수 없지만 답에 들어갈 연산자는 n-1개 이므로 브루트 포스로 해결가능하다!)

각각이 몇 개 씩인지 고정되어있지 않기 때문에 이 문자를 다 쓸때까지 연산을 사용하고 이후에 사용한 연산의 개수가 N-1일 때 그 값을 리턴한 후 최대, 최소랑 비교하면된다.

 

소스 코드

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
 
 
pair<intint> calc(vector<int> &a, int idx, int cur, int plus, int minus, int mul, int div) {
    int n = a.size();
    if (idx == n) return make_pair(cur, cur);
    vector<pair<intint> >res;
    if (plus > 0) {
        res.push_back(calc(a, idx + 1, cur+a[idx], plus - 1, minus, mul, div));
    }
    if (minus > 0) {
        res.push_back(calc(a, idx + 1, cur - a[idx], plus, minus - 1, mul, div));
    }
    if (mul > 0) {
        res.push_back(calc(a, idx + 1, cur * a[idx], plus, minus, mul - 1, div));
    }
    if (div > 0) {
        res.push_back(calc(a, idx + 1, cur / a[idx], plus, minus, mul, div - 1));
    }
    auto ans = res[0];
    for (auto p : res) {
        if (ans.first < p.first) {
            ans.first = p.first;
        }
        if (ans.second > p.second) {
            ans.second = p.second;
        }
    }
    return ans;
}
int main() {
    scanf("%d"&n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d"&a[i]);
    }
    int plus, minus, mul, div;
    scanf("%d %d %d %d"&plus, &minus, &mul, &div);
    auto p = calc(a, 1, a[0], plus, minus, mul, div);
    cout << p.first << "\n";
    cout << p.second;
    return 0;
}
cs

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~

'백준 문제풀이' 카테고리의 다른 글

백준 14503번 로봇 청소기  (0) 2020.01.27
백준 14499번 주사위 굴리기  (0) 2020.01.27
백준 1248번 맞춰봐  (0) 2020.01.20
백준 15661번 링크와 스타트  (0) 2020.01.20
백준 9019번 DSLR  (0) 2020.01.20