알고리즘/백준

[C++] 백준 7490 0 만들기

이영재의오른발 2023. 1. 6. 11:13
반응형

 

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
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
 
using namespace std;
 
int t, n;
vector<string> result;
 
void calculate(vector<string> vec, string str) {
    stack<int> stk;
    stack<string> op;
 
    for (int i = vec.size() - 1; i >= 0; i--) {                                                                
        if (vec[i] == "+" || vec[i] == "-") {
            op.push(vec[i]);
        }
        else {
            stk.push(stoi(vec[i]));
        }
    }
    int s = op.size();
    for (int i = 0; i < s; i++) {
        string c = op.top();
        op.pop();
        if (c == "+") {
            int a = stk.top();
            stk.pop();
            int b = stk.top();
            stk.pop();
            stk.push(a + b);
        }
        else if (c == "-") {
            int a = stk.top();
            stk.pop();
            int b = stk.top();
            stk.pop();
            stk.push(a - b);
        }
    }
 
    if (stk.top() == 0) {
        result.push_back(str);
    }
}
 
void dfs(string str, string a, int cnt) {
    if (cnt == n) {
        str = str + to_string(n);
        a = a + to_string(n);
        vector<string> vec;
        string b = "";
        for (int i = 0; i < str.length(); i++) {
            if (str[i] == '+' || str[i] == '-') {
                vec.push_back(b);
                string rem = "";
                rem = rem + str[i];
                vec.push_back(rem);
                b = "";
            }
            else {
                b = b + str[i];
            }
        }
        vec.push_back(b);
 
 
        calculate(vec, a);
        return;
    }
 
    // 0 == +, 1 == 공백, 2 == - 
    for (int i = 0; i < 3; i++) {
        string tmp = str + to_string(cnt);
        string k = a + to_string(cnt);
 
        if (i == 0) {
            tmp = tmp + "+";
            k = k + "+";
        }
        else if (i == 1) {
            k = k + " ";
        }
        else if (i == 2) {
            tmp = tmp + "-";
            k = k + "-";
        }
        dfs(tmp, k, cnt + 1);
    }
}
 
void input() {
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        dfs("", "", 1);
        sort(result.begin(), result.end());
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << endl;
        }
        result.clear();
        cout << '\n';
    }
}
 
int main() {
    input();
 
}
cs

 

 

문자열  + 완전탐색을 이용하는 문제 

 

N 의 값이 최대 9 이므로 최대 시간 복잡도는 O(3^9) 로 완전탐색이 가능하다

 

1. N 의 값을 입력받아 완전탐색 실행

 

1
2
cin >> n;
dfs("", "", 1);                                                            
cs

** DFS 인자로 공백 문자열 두개를 주는 이유

 

문제에서 수식을 출력할때 공백을 포함하라 했는데 공백을 포함하게되면 스택을 이용한 계산에 문제가 생기기 때문에

첫번째 인자는 공백을 포함하지 않는 문자열 (스택 계산을 위함), 두번째 인자는 공백을 포함하는 문자열(출력을 위함)을 만들었다.

 

2. 완전탐색을 이용해 계산한 후 스택의 최종값이 0 이면 결과 벡터에 저장

3. sort 함수를 이용해 결과 메소드 정렬 후 출력

4. 테스트 케이스 수 만큼 반복

 

728x90
반응형