백준 16637 _ 괄호 추가하기

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

16637번: 괄호 추가하기

---

✨ 내 소스 코드

#include <iostream>
#include <string>
using namespace std;
string s;
int N, max_n = -987654321987654321;

int calcu(char op, int n1, int n2) {
	int result = 0;
	switch (op)
	{
	case '+':
		result = n1 + n2;
		break;
	case '-':
		result = n1 - n2;
		break;
	case '*':
		result = n1 * n2;
		break;

	}
	return result;
}

void func(int n, int sum, char op) {
	//현재 위치가 문자열 길이보다 크면 종료
	if (n > N - 1) {
		if (max_n < sum) {
			max_n = sum;
		}
		return;
	}
    //괄호 계산
	if (n + 2 < N) {
		int temp = calcu(s[n + 1], s[n] - '0', s[n + 2] - '0');
        //n+2가 마지막 숫자이고 n+3은 범위를 넘었을 경우 처리, 즉 괄호로 더 묶지 못하는 경우
		if (n + 3 > N - 1) {
			func(n + 4, calcu(op, sum, temp), 'x');
		}
        //뒤에 괄호로 더 묶을 수 있는 경우 처리
		else {
			func(n + 4, calcu(op, sum, temp), s[n + 3]);
		}
	}
    //괄호 없이 계산
	func(n + 2, calcu(op, sum, s[n] - '0'), s[n + 1]);

}

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

	cin >> N;
	cin >> s;

	func(0, 0, '+');
	cout << max_n;

	return 0;
}

 

🙏 문제 풀이

재귀를 돌려서 모든 경우를 다 탐색해보고 그 중에서 최대값을 찾는다

'정답은 2^31보다 작고, -2^31보다 크다' 라는 조건이 있기 때문에 max_n의 초기값을 -2^31로 설정

 

 

+) 다음에는 초기값 설정 대신 max()함수 사용해서 답 구하는 걸 연습해야 될 듯

 

⭐ 문제 풀이 결과