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

27 Oct 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 16637 : 괄호 추가하기(링크)

알고리즘

1. 완전탐색
2. 그래프이론 (DAG)
3. Index 기반 탐색

풀이

1. idx 기반 탐색을 진행하기 위해 숫자와 연산기호를 같은 인덱스에 배치하여 비교해 나갈 수 있다
2. 완전 탐색을 끝내는 기저사례는 숫자 개수만큼 연산을 진행했을 때
3. idx 기반으로 앞에서부터 연산했을 때와 뒤에서부터 연산해서 앞 숫자와 다시 연산했을 때 갈래를 나눈다
   • 오버플로우는 항상 의식해서 체크해준다

코드

// BOJ-16637 : 괄호 추가하기
#include<bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
int n, res = -INF;
vector<int> num;
vector<char> op;

int oper(char op, int b, int c)
{
	if (op == '+') return b + c;
	if (op == '-') return b - c;
	if (op == '*') return b * c;
}

// DAG (Directed Acyclic Graph) - 완전탐색, idx 기반 탐색
void go(int here, int _num)
{
	// 기저 사례
	if (here == num.size() - 1)
	{
		res = max(res, _num);
		return;
	}

	go(here + 1, oper(op[here], _num, num[here + 1])); // 앞에서 부터
	if (here + 2 <= num.size() - 1) // 오버플로우 체크
	{
		int tmp = oper(op[here + 1], num[here + 1], num[here + 2]);
		go(here + 2, oper(op[here], _num, tmp)); // 뒤쪽부터 연산
	}
}

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

	cin >> n;
	string str;
	cin >> str;

	for(int i = 0; i < str.size(); i++)
	{
		if (i % 2 == 0) num.push_back(str[i] - '0');
		else op.push_back(str[i]);
	}

	go(0, num[0]); // 초기 값 num[0]부터 오른쪽으로 방향성을 가지고 탐색

	cout << res << '\n';

	return 0;
}

평가

• 누적합을 구하는 구하는 문제로 방향성이 있고 사이클이 없는 그래프의 특성을 가지고 완전탐색 알고리즘을 사용할 수 있다
• idx 기반 문제의 경우 계산하기 편하게 나누어서 생각하는 습관을 들인다