[ 백준-16637 / 완전탐색 ] 괄호 추가하기 (삼성 기출)

1. 문제

---

16637번: 괄호 추가하기

문제

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

예제 입력 1 복사

9 3+8*7-9*2

예제 출력 1 복사

136

 

 

2. 소스코드

---

1회차

 

- 괄호를 어떻게 넣을 것인가에서 막혔던 문제. 괄호끼리는 범위가 겹칠 수 없다는 조건이 있다. 그래서 숫자 앞에만 여는 괄호 "(" 를 놓고, 다음칸에는 닫는 괄호를 자동으로 ")" 놓은 뒤,  이를 배열에 저장해서 풀었다. 풀다보니 배열 인덱스가 엄청 햇갈리는 등 직관적이지도 않은데, 시간 복잡도도 안좋은 더러운 코드가 됬다.

 

- 문제를 너무 정직하게 구현함. 추상화가 부족했음. (괄호를 진짜로 삽입하고 저장, 비교 계산)

 

- 수식을 cin으로 받은 것 부터 아쉬움. scanf 로 수와 기호를 구분해 받았다면 훨씬 좋았을 것. scanf("%d%c", .....);

 

- DFS 로직 틀림. 중복이 발생함.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int answer;

int N;
string formular;
int ans;
struct Info {
    char arr[20];
    int res;
}info;
bool first = true;
queue <char> cal;
 
int opcal(int a, int b, char op) {

    switch (op)
    {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
    }
}

void dfs(Info info, int idx, int cnt) {

    if (cnt >= N / 2) {
        int numcnt = 0;
        for (int i = 0; i < formular.size(); i++) {
            if (isdigit(formular[i])) {

                if (info.arr[numcnt] == '(') {
                    cal.push(info.arr[numcnt]);
                    cal.push(formular[i]);
                }
                else if (info.arr[numcnt] == ')') {
                    cal.push(formular[i]);
                    cal.push(info.arr[numcnt]);
                }
                else {
                    cal.push(formular[i]);
                }
                numcnt++;

            }
            else cal.push(formular[i]);
        }
        queue <char > temp = cal;
        while (!temp.empty()) {
            cout << temp.front();
   
            temp.pop();
        }
        cout << '\n';
 
        int sum = 0;

        queue <int> number;
        queue <char> oper;
        while (!cal.empty()) {

            char ch = cal.front(); cal.pop();
            if (ch == '(') {
                char a, b, c;
                a = cal.front() - '0'; cal.pop();
                b = cal.front(); cal.pop();
                c = cal.front() - '0'; cal.pop();
                number.push(opcal(a, c, b));
                cal.pop();
            }
            else if (isdigit(ch)) {
                number.push(ch - '0');
            }
            else oper.push(ch);
        }

        int a, b;
        char op;
        a = number.front(); number.pop();
        while (!number.empty()) {
            b = number.front(); number.pop();
            op = oper.front(); oper.pop();
            a = opcal(a, b, op);
        }
 
        sum = a;
        if (ans < sum or first)
        {
            ans = sum;
            first = false;
        }
        return;
    }

    //숫자 끝까지
    // N/2 + 1까지이지만 마지막 수는 괄호를 넣을 수 없다.
    //이미 괄호라 넣을 수 없음
  
    if (info.arr[idx] == NULL and info.arr[idx + 1] == NULL){
        info.arr[idx] = '(';
        info.arr[idx + 1] = ')'; 
    }
    dfs(info, idx + 1, cnt + 1);
    
    if (info.arr[idx] != NULL and info.arr[idx + 1] != NULL) {
        info.arr[idx] = NULL;
        info.arr[idx + 1] = NULL;
    }
    dfs(info, idx + 1, cnt + 1);
 
 
}

int main() {

    cin >> N;
    cin >> formular;
       
    if (N == 3) {
        ans = opcal(formular[0] - '0', formular[2] - '0', formular[1]);
    }
    else dfs(info, 0,0);

    cout << ans << '\n';

    return 0;
}

 

 

2회차

 

- 계산기 문제는 숫자와 기호를 분리하는 것이 좋다는 것을 알게됨. 숫자와 기호 분리후 계산. 괄호와 기호는 합치지 않음.

- 1회차때의 처참한 숫자 계산 로직 변경.

- DFS 중복 제거.

 

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;
int answer;

int N, ans = INT_MIN;
string formular;
struct Info {
    char arr[20];
    int res;
}info;

int opcal(int a, int b, char op) {

    switch (op)
    {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
    }
}

void dfs(Info info, int idx ) {

    if (idx >= N / 2) {
        //수식 분리
        vector <int> number;
        vector <char> oper;
        for (int i = 0; i < formular.size(); i++) {
            char ch = formular[i];
            if (isdigit(ch)) number.push_back(ch - '0');
            else {
                oper.push_back(ch);
            }  
        }
        // 수식 계산
        int res = number[0];
        for (int i = 0; i < N / 2; ++i) { 
            if (info.arr[i + 1] == '(') {//다음 수가 괄호라면
                int temp = opcal(number[i + 1], number[i + 2], oper[i + 1]);
                res = opcal(res, temp, oper[i]); i++;
            }
            else 
                res = opcal(res, number[i + 1], oper[i]);
        }
        if (ans < res) ans = res;
        return;
    }

    for (int i = idx; i < N / 2; ++i){//마지막 수에는 괄호를 넣을 수 없다.
        if (i > 0 and info.arr[i - 1]) continue;
        info.arr[i] = '(';
        dfs(info, i + 1);
        info.arr[i] = NULL;
    }
    dfs(info, N/2); 
    // 더 이상 넣지 못하는 경우. 강제로 종료 후 계산.
} 

int main() {

    cin >> N;
    cin >> formular;

    dfs(info, 0);

    cout << ans << '\n';
    return 0;
}