[C++] 백준 16637 괄호 추가하기

문제 링크

---

www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

접근 방법

---

 문제를 해결하면서 골치 아팠던 3가지 유의사항이 있었다.

 

※ 유의 사항

1. 입력받는 수의 갯수가 1개일 경우, 해당 값이 정답이 되어야 함

2. 문제에서 요구하는 최댓값이 음수 일 수 있기 때문에, 정답의 초기값을 0으로 설정하지 않는다.

3. 원인은 파악 안했으나, 하단의 소스코드가 문제를 발생시킴.

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

 

 

1. 기본적으로 재귀 함수를 사용하여 괄호 추가가 가능한 모든 경우의 수에 대해 탐색하였고,  연산자와 숫자를 따로 분리하여 관리 하였다.

 

 괄호 추가가 가능한 모든 경우의 수를 탐색하는 코드이다. 

void solve(int now) {

	for (int i = now; i < numbers.size() - 1; i++) {
		if (visited[i] == false) {
			visited[i] = visited[i + 1] = true;
            		ans = max(ans, calc_result());
			solve(i + 1);
			visited[i] = visited[i + 1] = false;	
		}
	}
}

visited[]는 괄호에 감싸져 있는 숫자를 체크하는 배열이다. 문제의 조건에서 괄호안에는 하나의 연산자만 포함한다고 했으므로, 인접한 두 숫자에 대해서 방문체크를 하게 된다. 이후 calc_result()라는 함수안에서 현제 괄호를 포함한 전체 수식을 계산하게 된다.

 

calc_result()

long long calc_result() {

	vector <long long> tmpnumbers;
	vector <char> tmptokens;
	vector <bool> visited_t(tokens.size());
	long long result;
	
    //괄호 값 먼저 계산
	for (int i = 0; i < numbers.size(); i++) {
		if (i < numbers.size() -1 && visited[i] && visited[i + 1]) {
			tmpnumbers.push_back(part_calc(numbers[i], numbers[i + 1], tokens[i]));
			visited_t[i] = true;
			i += 1;
		}
		else 
			tmpnumbers.push_back(numbers[i]);
	}
    
    //괄호에서 사용하고 남은 연산자 배열
	for (int i = 0; i < tokens.size(); i++) 
		if (!visited_t[i]) 
			tmptokens.push_back(tokens[i]);

	//괄호의 계산이 종료 된 이후, 전체 수식 계산 
	result = tmpnumbers[0];
	for (int i = 1; i < tmpnumbers.size(); i++) 
		result = part_calc(result, tmpnumbers[i], tmptokens[i - 1]);

	return result;
}

 

 

 괄호값을 먼저 계산하여 수를 정리하고, 괄호안에서 사용된 연산자를 제외한 연산자를 모아 다시 수식 생성

입력숫자(numbers) -> 정리숫자(tmpnumbers) , 입력연산자(tokens) -> 정리연산자(tmptokens)

 

이 함수에는 3가지 과정이 존재한다. 

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

1. 괄호 값 먼저 계산

   앞서 visited[]를 통해 괄호의 위치를 체크하였기 때문에 괄호가 포함된 (a ,(+-*), b)를 part_calc() 함수에서 계산하며,

   괄호안에서 사용된 연산자를 visited_t[]로 사용표시를 한다. 또한 괄호가 정리된 이후 계산 될 새로운 숫자 벡터             tmpnumbers에 push한다. 

   tmpnumbers={1, 5, 9} -> 2와3 사이의 '+'위치 체크, 4와5 사이의 '+'위치 체크, visited_t[1]=visited_t[3]=true

   

2. 괄호에 포함되지 않아 사용되지 않은 연산자를 tmptokens에 담는다.

    tmptokens={-, -}

 

3. 정리된 전체 수식을 계산한다.

 

소스 코드

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector <long long> numbers;
vector <char> tokens;
bool visited[20];
long long ans = -9999999999;

long long part_calc(long long a, long long b, char token) {

	long long result = 0;
	if (token == '*')
		result = a * b;
	else if (token == '+') 
		result = a + b;
	else if (token == '-') 
		result = a - b;

	return result;
}

long long calc_result() {

	vector <long long> tmpnumbers;
	vector <char> tmptokens;
	vector <bool> visited_t(tokens.size());
	long long result;
	
	for (int i = 0; i < numbers.size(); i++) {
		if (i < numbers.size() -1 && visited[i] && visited[i + 1]) {
			tmpnumbers.push_back(part_calc(numbers[i], numbers[i + 1], tokens[i]));
			visited_t[i] = true;
			i += 1;
		}
		else 
			tmpnumbers.push_back(numbers[i]);
	}
	for (int i = 0; i < tokens.size(); i++) 
		if (!visited_t[i]) 
			tmptokens.push_back(tokens[i]);

	result = tmpnumbers[0];
	for (int i = 1; i < tmpnumbers.size(); i++) 
		result = part_calc(result, tmpnumbers[i], tmptokens[i - 1]);

	return result;
}

void solve(int now) {

	for (int i = now; i < numbers.size() - 1; i++) {
		if (visited[i] == false) {
			visited[i] = visited[i + 1] = true;
			ans = max(ans, calc_result());
			solve(i + 1);
			visited[i] = visited[i + 1] = false;	
		}
	}
	
}

int main() {

	cin >> n;
	for (int i = 0; i <= n/2; i++) {
		int num;
		char token;
		scanf("%1d", &num);
		numbers.push_back(num);
		if (n / 2 != i) {
			scanf("%c", &token);
			tokens.push_back(token);
		}
	}
	solve(0);
	if (n == 1)
		cout << numbers[0];
	else
		cout << ans;
}

개발 환경 : VS2019

질문, 지적 환영합니다!