펭로그

[C++] 백준 BOJ 14888 연산자 끼워넣기 (SWEA 4008 숫자 만들기) 본문

Study/PS(Algorithm)

[C++] 백준 BOJ 14888 연산자 끼워넣기 (SWEA 4008 숫자 만들기)

노랑펭귄 2018. 10. 20. 12:03

문제링크 : https://noj.am/14888

문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH


<아래 풀이는 백준 14888 문제 기준>

DFS를 이용하여 완전탐색을 시행한 브루트포스 문제이다.

각 시행 마다 + - * / 연산 모두를 다음 탐색에서 시행한다.

구조를 간단하게 하기 위하여 구조체 안에 생성자를 통해서 다음 노드의 구조체를 만들어준다.

이 때, 입력받은 연산이 무엇인지를 확인하여 + - * / 의 연산을 구분해서 데이터를 새로 만들어준다.


재귀 호출 시마다 4번의 추가 호출이 있기 때문에 시간 복잡도는 O(4^N)이다.

문제에서 N은 11까지라는 조건이 있으므로 4^11 = 4,194,304 이다.

최대 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
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// BOJ_14888 연산자 끼워넣기
#include <iostream>
#include <vector>
 
using namespace std;
 
int N; // 숫자 갯수
vector<int> arr; // 숫자 배열
int oper[4]; // + - * / 연산자 갯수
 
int maxNum = INT32_MIN;
int minNum = INT32_MAX;
 
int min(int a, int b) {
    return a > b ? b : a;
}
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
struct info {
    int idx; // 현재 탐색중인 인덱스
    int pl; // 덧셈 연산자 갯수
    int mi; // 뺄셈 연산자 갯수
    int mul;// 곱셈 연산자 갯수
    int div;// 나눗셈 연산자 갯수
    int result; // 현재 누적 연산자 갯수
 
    // 초기화를 위한 생성자
    info(int a, int b, int c, int d, int e, int f)
            : idx(a), pl(b), mi(c), mul(d), div(e), result(f) {};
 
    // 다음 노드의 연산 결과를 만들어주는 생성자
    info(info &node, string a) {
        // node로 부터 받은 값 저장
        idx = node.idx;
        pl = node.pl;
        mi = node.mi;
        mul = node.mul;
        div = node.div;
        result = node.result;
        // 연산 결과를 저장함과 동시에 idx 증가
        if (a == "pl") {
            result += arr[++idx];
            pl--;
        }
        else if (a == "mi") {
            result -= arr[++idx];
            mi--;
        }
        else if (a == "mul") {
            result *= arr[++idx];
            mul--;
        }
        else if (a == "div") {
            result /= arr[++idx];
            div--;
        }
    }
};
 
void dfs(info node) {
    // 각 연산 수행
    if (node.pl > 0)
        dfs({node, "pl"});
    if (node.mi > 0)
        dfs({node, "mi"});
    if (node.mul > 0)
        dfs({node, "mul"});
    if (node.div > 0)
        dfs({node, "div"});
    // 최대값, 최소값 저장
    if (node.idx >= N - 1) {
        maxNum = max(maxNum, node.result);
        minNum = min(minNum, node.result);
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    cin >> N;
    arr = vector<int>(N);
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    for (int i = 0; i < 4; i++)
        cin >> oper[i];
 
    info init = {0, oper[0], oper[1], oper[2], oper[3], arr[0]};
    dfs(init);
 
    cout << maxNum << "\n" << minNum;
 
    return 0;
}
cs


<SWEA 4008 소스코드>


저작자표시

'Study > PS(Algorithm)' 카테고리의 다른 글

[C++] SWEA 1949 등산로 조성  (0) 2018.10.22
[C++] 백준 BOJ 16234 인구 이동  (0) 2018.10.21
[C++] 백준 BOJ 14891 톱니바퀴 (SWEA 4013 특이한 자석)  (0) 2018.10.19
[C++] 문자열 계산기  (6) 2018.10.18
[C++] 백준 BOJ 14890 경사로 (SWEA 4014 활주로 건설)  (0) 2018.10.13
'Study/PS(Algorithm)' Related Articles more
Comments