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

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

16637번: 괄호 추가하기

백준 사이트의 16637번 문제, "괄호 추가하기" 문제 풀이다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

짧은 문제여서 전체 캡쳐를 가져왔다.

- 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다.
- 둘째 줄에는 수식이 주어진다.
- 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다.

- 연산자 우선순위는 모두 동일, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산
- 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다.
- 괄호 안에는 연산자가 하나만 들어 있어야 한다.
- 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

- 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성

---

1. 문제풀이 아이디어

- 최댓값을 구해야하므로 DFS로 풀자.
- 괄호를 친다는건 그 연산자를 그냥 우선으로 계산한다는 개념
- 앞에서부터 연산자 기준으로 하나씩 확인하는데, 두가지로 분기를한다.
  1. 그냥 원래대로 계산
  2. 이번 연산자 다음 연산자에 괄호가 있어 그거먼저 계산하기

---

2. 코드 핵심 부분

1) 두 경우로 분기하며 문자열 끝까지 가는 DFS 함수

   사실 이게 풀이의 전부인 함수인데 인자 입력과 범위만 조심하면 쉬운 문제였다.

// 두가지로 분기하며 문자열 끝까지 가는 DFS
// 연산자인덱스, 끝인덱스, 합
void dfs(int op, int ed, int sum) {

	if (op >= N) {

		if (sum > ans)
			ans = sum;

		return;
	}

	// 1. 그냥 그대로 계산
	dfs(op + 2, ed + 2, calc(sum, op, str[ed] - '0'));

	// 2. 다음 연산자에 괄호 (단, 다음연산자가 존재하나 확인해야함)
	if (op < N - 3) {
		// 연산자 두개 처리해서 +4 인덱스로 이동한다.
		dfs(op + 4, ed + 4, calc(sum, op, calc(str[ed] -'0', op + 2, str[ed + 2] - '0')));
	}
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/*
1. 문제읽기
	- 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다.
	- 둘째 줄에는 수식이 주어진다.
	- 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다.

	- 연산자 우선순위는 모두 동일, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산
	- 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다.
	- 괄호 안에는 연산자가 하나만 들어 있어야 한다.
	- 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

	- 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성
*/

/*
2. 아이디어
	- 최댓값을 구해야하므로 DFS로 풀자.
	- 괄호를 친다는건 그 연산자를 그냥 우선으로 계산한다는 개념
	- 앞에서부터 연산자 기준으로 하나씩 확인하는데,
	  두가지로 분기를한다.
	  1. 그냥 원래대로 계산
	  2. 이번 연산자 다음 연산자에 괄호가 있어 그거먼저 계산하기
*/

// 필요 인자들
int ans = -21e8;
int N;
string str;

// 값 입력받는 함수
void input() {
	cin >> N;
	cin >> str;
}

// 계산 처리하는 함수
int calc(int left, int op, int right) {
	// 연산자를 받아서 그걸로 분기해서 계산하고 return
	char nowOp = str[op];

	if (nowOp == '+') {
		return (left + right);
	}
	else if (nowOp == '-') {
		return (left - right);
	}
	else if (nowOp == '*') {
		return (left * right);
	}
}

// 두가지로 분기하며 문자열 끝까지 가는 DFS
// 연산자인덱스, 끝인덱스, 합
void dfs(int op, int ed, int sum) {

	if (op >= N) {

		if (sum > ans)
			ans = sum;

		return;
	}

	// 1. 그냥 그대로 계산
	dfs(op + 2, ed + 2, calc(sum, op, str[ed] - '0'));

	// 2. 다음 연산자에 괄호 (단, 다음연산자가 존재하나 확인해야함)
	if (op < N - 3) {
		// 연산자 두개 처리해서 +4 인덱스로 이동한다.
		dfs(op + 4, ed + 4, calc(sum, op, calc(str[ed] -'0', op + 2, str[ed + 2] - '0')));
	}
}

// 메인함수
int main() {

	// input
	input();

	// solve -> 시작 숫자를 sum에 넣고 dfs시작함.
	dfs(1, 2, str[0] - '0');

	// output
	cout << ans;
	
	return 0;
}

---

4. 문제 풀이를 마치며..

채점 결과

DFS까지는 잘 떠올랐는데 그 이후에 많이 헤맨 문제이다...

처음에는 DFS로 우선 괄호를 다 선택하고 계산을 한번에 하려하니깐 매우 막막하였다.

계산을 하면서 나아가는것이 훨씬 좋은 방법이었다.

 

재귀적으로 생각해야 쉽게 풀 수 있는 문제였다.

 

결국 한 괄호안에는 연산자가 하나밖에 있을 수 없기때문에,

딱 지금연산자와 다음연산자, 두가지 연산자만 무엇을 우선할지 판단하여 계산한다음

다음 DFS로 넘어가는 방법으로 풀 수 있었다.

 

DFS는 나름 자신 있었는데 더욱 연습이 필요할듯...