백준(boj) 16637_괄호 추가하기 (파이썬, c++)

https://www.acmicpc.net/problem/16637

풀이

---

수식이 문자열로 주어진다. 피연산자는 0~9인 정수이므로 홀수번째 인덱스는 수식이고 짝수 번째 인덱스는 숫자인 것을 이용했다. solve() 함수를 이용해 완전 탐색 해줬는데 check 리스트를 이용해서 그 자리에 해당하는 수식이 켜져 있는지 꺼져있는지 확인 후 계산해 주었다. 이때 계산은 deque를 사용해 주었다.

python3

from sys import*
from collections import*
input = lambda:stdin.readline().strip()
def cal2(n1, op, n2):    #연산 받아서 계산
    if op == '+': return n1+n2
    if op == '-': return n1-n2
    if op == '*': return n1*n2
def cal():
    q=deque()                        #deque 사용
    i=0
    while 1:                         #괄호 먼저 처리
        if i==n: break                
        if i%2 != 0 and check[i]:    #수식 자리이고, check 켜져있으면(괄호이면)
            q.append(cal2(int(q.pop()), a[i], int(a[i+1])))    #계산해서 넣어줌
            i+=1                     #윗줄에서 계산할때 i+1 썼으니까 i+=1 해줌
        else:                        #수식이 아니거나 안켜져 있으면 그냥 넣어줌
            q.append(a[i])
        i+=1
    while q:                         #괄호 처리가 완료된 수식 처리
        if len(q)==1: break          #q에 숫자 하나만 있으면 끝
        q.appendleft(cal2(int(q.popleft()), q.popleft(), int(q.popleft())))
    return q[0]
def solve(pos=1):                    #완탐
    global res
    if pos >= n:return cal()         #n개 이상=> 끝에 다다름, 계산해줌
    check[pos]=1
    res = max(res, solve(pos+4))     #수식을 선택했으면, 다다음 수식으로(문제에 괄호 겹치지 말라고 주어짐)
    check[pos]=0
    res = max(res, solve(pos+2))     #주어진 문자열에서 수식 2칸씩 띄어져 있음
    return res
n=int(input())
res=int(-1e10)
check=[0]*n
a=input()
print(solve())

C++

//오류남 deque 자료형 선언 찾아보고 수정해야함
#include<cstdio>
#include<algorithm>
#include<deque>
#include<memory.h>
using namespace std;
const int SIZE=20;
bool check[SIZE];
char a[SIZE];
int n, res;
int cal2(int n1, char op, int n2){
    if(op == '+') return n1+n2;
    if(op == '-') return n1-n2;
    if(op == '*') return n1*n2;
}
int cal(){
    deque<string> q;        //이 부분
    int i=0;
    while(1){
        if(i==n) break;
        if((i%2 != 0) && check[i]){
            int n1=int(q.back()); q.pop_back();
            q.push_back(cal2(n1, a[i], int(a[i+1])));
            i++;
        }
        else{
            q.push_back(a[i]);
        }
        i++;
    }
    while(!q.empty()){
        if(q.size()==1)break;
        int n1 = int(q.front());q.pop_front();
        char op = q.front();q.pop_front();
        int n2 = int(q.front());q.pop_front();
        q.push_front(cal2(n1, op, n2));
    }
    return q[0];
}
int solve(int pos){
    if(pos >= n) return cal();
    check[pos]=1;
    res = max(res, solve(pos+4));
    check[pos]=0;
    res = max(res, solve(pos+2));
    return res;
}
int main()
{
    res=-(1e9+1);
    scanf("%d", &n);
    memset(check, 0, sizeof(check));
    for(int i=0; i<n; i++){
        scanf("%c", &a[i]);
    }
    printf("%d", solve(1));
    return 0;
}

고찰

---

1.for문으로 range(n) 해놓고 중간에 계산하면 i+=1 해줬는데 i값 원하는대로 안변해서 while문으로 써줌.

2.음수가 답일수도 있는데 초기값 0으로 했다가 틀렸었음