[ Baekjoon ] 16637. 괄호 추가하기

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

16637번: 괄호 추가하기

풀이 방법

A op B 구조(A, B: operand, op: operator)에서 해당 연산을 괄호로 묶는 경우, 안 묶는 경우를 DFS로 완전 탐색한다. new_expr에 표현식을 완성해나가는데, 괄호를 묶는 경우는 연산을 해준 값을 바로 저장해준다. 이때, 연산을 해준 값이 10 이상일 수 있기 때문에 new_expr을 char형 배열이 아닌 int형 배열로 선언했다.

for (int i = idx; i < N - 2; n += 2, i += 2) {
    // apply bracket
    switch (expr[i + 1]) {
    case '+':
        new_expr[n] = (expr[i] - '0') + (expr[i + 2] - '0');
        break;
    case '-':
        new_expr[n] = (expr[i] - '0') - (expr[i + 2] - '0');
        break;
    case '*':
        new_expr[n] = (expr[i] - '0') * (expr[i + 2] - '0');
        break;
    }
    new_expr[n + 1] = expr[i + 3];
    max_result(i + 4, new_expr, n + 2); // recursive

    // doesn't apply bracket
    new_expr[n] = expr[i] - '0';
    new_expr[n + 1] = expr[i + 1];
    max_result(i + 2, new_expr, n + 2); // recursive
}

 

표현식을 완성하면 연산자의 우선순위 없이 앞에서부터 계산한다.

int compute(int* expression, int n) {
	int result = expression[0];
	for (int i = 1; i < n; i += 2) {
		switch (expression[i]) {
		case '+':
			result += expression[i + 1];
			break;
		case '-':
			result -= expression[i + 1];
			break;
		case '*':
			result *= expression[i + 1];
			break;
		}
	}
	return result;
}

 

전체 코드는 여기서 확인할 수 있다.