[BOJ] 백준 16637. 괄호 추가하기

▶문제설명

[BOJ] 백준 16637. 괄호 추가하기

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

▶ 설계

---

브루트 포스 문제이다. DFS로 해결할 수 있을 것으로 보인다.

1+2-3*4 

위 식을 예로 들어,
문제의 조건에 따라서 괄호를 씌울 수 있는 모든 경우를 나열해보자.

1+2는 괄호를 씌우나 마나 결과가 같다. 가장 앞에 위치하기 때문이다.

1+2-3*4+5
1+2-3*(4+5)
1+2-(3*4)+5

1+(2-3)*4+5

1+(2-3)*(4+5)

이렇게 5 가지 경우가 있다.

함수를 두 번 재귀호출 하여 구현할 수 있다.

1. 이전 계산 결과와 오른쪽에 있는 피연산자를 피연산자로 하여 현재 가리키는 연산자의 연산을 수행하는 함수 

(왼쪽부터 순서대로 계산하게 됨)

2. 이전 계산 결과와 오른쪽에 있는 연산자의 연산 수행 결과를 피연산자로 하여 현재 가리키는 연산자의 연산을 수행하는 함수 

(+,-,*은 이항 연산자이므로 양쪽으로 하나의 피연산자가 필요함)

[재귀 탈출 조건]

연산자의 인덱스를 초과하여 현재 가리키는 연산자가 없는 경우

계산된 결과를 비교하여 최대값으로 업데이트하는 작업을 수행한 뒤 종료한다.

▶ 구현

---

우선 메인문을 작성하자.

int main(){
    int N;
    string str;
    cin >> N >> str;
    for(int i=0; str[i] ;i++){
        if(str[i] == '+' || str[i] == '-' || str[i] == '*')
            ops.push_back(str[i]);
        else
            nums.push_back(str[i]-'0');
    }
    solve(nums[0],0);
    cout<<answer<<endl;
    return 0;
}

편의를 위해 연산자와 피연산자를 따로 저장했다.

연산자를 저장할 벡터 ops와 숫자를 저장할 벡터 nums를 사용했으며,

nums는 int형 자료를 저장하므로 -'0' 처리를 해주었다.

solve 함수를 호출하면 재귀 호출을 통해 answer에 답이 저장될 수 있도록 구현했다.

solve 함수를 살펴보자.

void solve(long long result, int nowOpIdx){
    if(nowOpIdx >= ops.size()){
        if(answer < result)
            answer = result;
        return;
    }
    long long res1 = calc(ops[nowOpIdx], result, nums[nowOpIdx+1]);
    solve(res1, nowOpIdx+1);
    
    if(nowOpIdx+1 < ops.size()){
        long long res2 = calc(ops[nowOpIdx+1], nums[nowOpIdx+1], nums[nowOpIdx+2]);
        solve(calc(ops[nowOpIdx],result,res2), nowOpIdx+2);
    }
}

누적 계산 결과를 저장할 result와 현재 연산자의 인덱스를 나타내는 nowOpIdx를 매개변수로 받는다.

현재 연산자의 인덱스를 초과할 때 answer를 갱신하고 재귀호출을 종료하도록 구현했다. (line 2~6)

연산자의 개수보다 피연산자의 개수가 하나 더 많을 수 밖에 없으므로 line 7 의 res1을 구하는 연산에서 인덱스를 초과하는 일은 발생하지 않는다.

calc 함수는 연산자와 피 연산자 두 개를 순서대로 받아서 연산자에 맞는 계산 결과를 반환한다.

line 8 에서 [설계]에서 설명했던 1번 재귀 호출을 수행한다.

하지만 line 11 의 res2를 구하는 연산에서는 인덱스를 초과하는 일이 발생할 수도 있다.

nowOpIdx+1 < ops.size()를 만족하지 못하면 nums[nowOpIdx+2] 에서 인덱스가 초과되어 원치않는 결과를 얻게 되므로 반드시 처리해주어야 한다.

line 12 에서 [설계]에서 설명했던 2번 재귀 호출을 수행한다.

calc 함수를 살펴보자.

long long calc(char op, long long n1, long long n2){
    if(op == '+')
        return n1+n2;
    else if(op == '-')
        return n1-n2;
    else
        return n1*n2;
}

설명이 필요 없을 정도로 간단하게 구현되어있다.

▶ 결과

---

▶Solution

---

[소스코드 보기]