백준 16637 괄호 추가하기

문제 URL : https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

문제 접근법 : 

 

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

//By 콩순이냉장고 #include<bits/stdc++.h> using namespace std; #define ll long long int n; string s; ll res = INT_MIN; ll cal(ll a, ll b, char op) {     if (op == '+')         return a + b;     if (op == '-')         return a - b;     return a * b; } void dfs(int idx = 1, ll sum = 0) {     if (idx >= n) {         res = max(sum, res);         return;     }     ll temp = cal(sum, s[idx] - '0', s[idx - 1]);     dfs(idx + 2, temp);     if (idx < n - 2) {         temp = cal(s[idx] - '0', s[idx + 2] - '0', s[idx + 1]);         temp = cal(sum, temp, s[idx - 1]);         dfs(idx + 4, temp);     } } void input() {     cin >> n;     cin >> s;     s = "+" + s;     n++; } void solve() {     dfs();     cout << res << endl; } int main() {       ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     //freopen("input.txt", "r", stdin);     input();     solve();   } Colored by Color Scripter

cs

 

 

궁금한점 혹은 모른느점 어떤질문이든 댓글은 언제나 환영입니다.