[Baekjoon(백준)][16637번] 괄호 추가하기(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "괄호 추가하기" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 수식에 괄호를 적절히 추가하여 만들 수 있는 식의 결과값 중 최대값을 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

16637번: 괄호 추가하기

문제개요

"괄호 추가하기" 문제는 수식에 괄호를 적절히 추가하여 만들 수 있는 식의 결과값 중 최대값을 찾는 문제입니다. 주어진 수식에는 정수와 연산자(+, -, *)만 포함되며, 연산자의 우선 순위를 무시하고 왼쪽부터 순서대로 계산합니다. 괄호를 추가하여 계산 순서를 바꿀 수 있으며, 중첩된 괄호는 사용할 수 없습니다.

해결전략

이 문제를 해결하기 위해 재귀 함수를 사용하여 모든 가능한 괄호의 위치를 시도해보고, 그 결과 중 최대값을 찾습니다. 괄호를 추가하는 것과 추가하지 않는 두 가지 경우를 각 단계에서 고려합니다. 괄호를 추가할 경우, 현재 숫자와 다음 숫자를 연산자로 계산한 결과를 다음 단계의 재귀 함수에 전달합니다. 괄호를 추가하지 않는 경우에는 현재까지의 계산 결과를 다음 단계의 재귀 함수에 전달합니다.

코드 구현

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

using namespace std;
int n, ret = INT_MIN; // 수식의 길이와 최대값을 저장할 변수
vector<int> numbers; // 수식에서 숫자만을 저장할 벡터
vector<char> opers; // 수식에서 연산자만을 저장할 벡터
string str; // 입력받을 수식 문자열

// 연산자에 따른 계산을 수행하는 함수
int Operator(char a, int b, int c) {
	if (a == '+') return b + c;
	if (a == '-') return b - c;
	if (a == '*') return b * c;
}

// 재귀 함수로 가능한 모든 괄호의 위치를 시도하며 최대값을 찾는 함수
void go(int index, int number) {
	if(index == numbers.size() - 1) { // 모든 수식을 계산했을 때
		ret = max(ret, number); // 최대값 갱신
		return;
	}
	// 괄호를 추가하지 않는 경우
	go(index + 1, Operator(opers[index],number, numbers[index + 1]));

	// 괄호를 추가하는 경우
	if (index + 2 <= numbers.size() - 1) {
		int temp = Operator(opers[index + 1], numbers[index + 1], numbers[index + 2]);
		go(index + 2, Operator(opers[index], number, temp));
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> str; // 수식의 길이와 수식 입력

	// 수식에서 숫자와 연산자를 분리하여 저장
	for (int i = 0; i < n; i++) {
		if (i % 2 == 0) numbers.push_back(str[i] - '0');
		else opers.push_back(str[i]);
	}
	// 재귀 함수 호출
	go(0, numbers[0]);
	cout << ret << "\n"; // 최대값 출력
}

코드 설명

이 코드는 입력받은 수식을 숫자와 연산자로 분리하여 저장한 뒤, 재귀 함수 go를 사용하여 모든 경우의 수를 탐색합니다. go 함수는 현재 위치(index)와 현재까지의 계산 결과(number)를 인자로 받으며, 기저 조건에서는 모든 수식을 계산한 경우 최대값을 갱신합니다. 괄호를 추가하는 경우와 추가하지 않는 경우를 분기하여 재귀 호출을 수행하며, 각각의 경우에 대해 연산 결과를 다음 단계로 전달합니다. 최종적으로 모든 경우의 수를 탐색한 후에는 ret에 저장된 최대값을 출력합니다.

결론

이 문제의 해결을 위해 재귀적 접근 방식을 통해 모든 경우의 수를 고려하는 방법을 사용했습니다. 괄호를 추가하여 연산의 순서를 변경하는 모든 방법을 시도해보고, 그 중 최대값을 찾아 해결했습니다.