티스토리 뷰

 

한번 풀어보려고했는데 한시간이나 걸렸따...

문제를 쉽게 해주기 위해 괄호는 하나의 연산자만 포함한다는걸 모르고 풀다가

나중에 보니 답이 다르게나온다~!

 

그리고 처음에 한자리수만 줘서 더 쉬운것같다

 

나처럼 복잡하게 푼 사람은 많이 없을듯..!

 

그럼 문제를 풀어보자!

우선 비트를 이용해서 짝수 인덱스인 숫자만 봐준다

괄호가 짝이 맞아야 하기 때문에 짝수개 있을 때만 넘겨준다!

110101이면 1~2 ,4~6이 괄호다!

 

괄호를 체크하고 solve 함수로 넘겨준다

그럼 solve는 괄호가 있는곳은 먼저 cal함수로 계산해주고 

마지막에 괄호가 없을 때를 계산해 답으로 넘겨준다

 

cal에서는 순서대로 앞에서 계산하기 때문에 덱으로 그냥 계산했다!

 

소스코드

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
#include <iostream>
#include <string>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
#define ll long long
int n;
ll ans = -1e18;
string arr;
vector<int> vt;
ll cal(deque<ll>& dq, deque<char>& op){
    while(!op.empty()){
        ll a = dq.front(); dq.pop_front();
        ll b = dq.front(); dq.pop_front();
        ll c = op.front(); op.pop_front();
        if(c=='+') a+=b;
        else if(c=='-') a-=b;
        else if(c=='*') a*=b;
        else a/=b;
        dq.push_front(a);
    }
    return dq.front();
}
ll solve(){
    deque<ll> dq;
    deque<char> op;
    int pos=0;
    for(int i=0;i<n;i++){
        if(pos<(int)vt.size() && vt[pos]==i){
            deque<ll> ddq;
            deque<char> oop;
            for(int j=vt[pos];j<=vt[pos+1];j++){
                if(j&1) oop.push_back(arr[j]);
                else ddq.push_back(arr[j]-'0');
            }
            dq.push_back(cal(ddq,oop));
            i=vt[pos+1]; pos+=2;
        }
        else{
            if(i&1) op.push_back(arr[i]);
            else dq.push_back(arr[i]-'0');
        }
    }
    return cal(dq,op);
}
 
int main(){
    scanf(" %d",&n);
    cin>>arr;
    int size = (n+1)/2;
    for(int i=0;i<(1<<size);i++){
        vt.clear();
        for(int j=0;j<size;j++){
            if(i&(1<<j)) vt.push_back(j*2);
        }
        if(vt.size()&1continue;
        bool c = true;
        for(int j=0;j<(int)vt.size()-1;j+=2){
            if(vt[j+1]-vt[j] != 2) c=false;
        }
        if(!c) continue;
        ans = max(ans,solve());
    }
    printf("%lld\n",ans);
}
 
 

'알고리즘 > BOJ' 카테고리의 다른 글

[백준] 17281 ⚾  (0) 2020.02.09
[백준] 17471 게리맨더링  (0) 2020.02.08
[백준] 12924 멋진 숫자 쌍  (0) 2020.02.07
[백준] 12919 A와 B 2  (0) 2020.02.07
[백준] 12945 재미있는 박스 정리  (0) 2020.02.05
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
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
글 보관함