[백준] 16637번: 괄호 추가하기

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

16637번: 괄호 추가하기

 

수식이 N개의 문자로 이루어져있으면,

N/2 개는 연산자고, N/2+1개는 피연산자이다.

여기에 괄호가 들어갈 수 있는 곳은 각 피연산자의 앞 또는 뒤이다.

나는 괄호의 끝을 넣어준다고 생각하고 놓을 수 있는 곳들을 생각해보았다. 

예제 1의 수식의 경우 저 주황색 칸들이 ')' 이 들어갈 수 있는 곳이다. 

어차피 두 개의 숫자만 묶을 수 있다고 했으니까 저렇게 생각하면 충분하다.

예를 들어, 만약 b에 ')'가 들어간다면 수식은 3+(8*7)-9*2 인 것이다.

주의할 점은 b에 ')가 들어가면 a에는 못들어간다는 점이다. 

 

DFS()

이렇게 이해했다면 이제 괄호가 들어갈 위치를 선정하면 된다.

DFS를 통해 저 4칸에 괄호가 들어가는 모든 경우를 탐색할 수 있다. 

void DFS(int idx) {

	if (idx > N / 2) {
		LLI res = Calculate();
		if (res > max) max = res;
		return;
	}

	// 재귀
	if((idx==0) || (idx-1 >= 0 && sel[idx-1] != 1)){
		sel[idx] = 1;
		DFS(idx + 1);
	}
	sel[idx] = 0;
	DFS(idx + 1);
}

sel[i]가 1이라는 것은 i위치에 ')'가 들어갔다는 것이다.

이렇게 N/2개의 괄호 후보 위치에 넣거나 안넣거나 정해줬다면 수식을 계산하기만 하면 된다.

 

Calculate()

수식 계산은 스택을 이용하면 된다. 

그래서 스택을 구현해서 피연산자(a) -> 연산자(op) -> 피연산자(b)의 순서로 스택에 넣고, 괄호가 있는지 확인한다.

괄호가 있다면 앞에 넣었던 b, op, a를 차례대로 꺼내면 된다. 

그 후에 실제 계산을 하는 r_calculate()라는 함수로 보내서 계산을 한다.

(내가 연산자를 int형으로 바꿔서 스택에 넣었기 때문에 별도의 함수를 만들어준 것이다.)

스택을 long long int형으로 만들고, 연산자와 피연산자를 모두 long long int형으로 만든 이유는,
음수 계산 때문이다. 예를 들어 3과 (-2) 를 더할 때, 가 숫자로 있으면 그냥 '+'로 바로 계산해버릴 수 있지만
문자로 되어있으면 '+'를 '-'로 바꾸는 복잡한 과정을 거쳐야 하기 때문이다. 

결과로 온 값은 다시 스택에 넣어주면 된다.

이 과정을 해서 괄호 식들을 쫙 정리한다

 

예를 들어 (3+8) * (7-9) * 2 라는 식이었다면 위의 부분을 거치고 나서 11 * -2 * 2로 정리되어 스택에 들어있다.

그럼 이제 앞에서부터 하나씩 빼서 계산해주면 된다. --> 이제는 앞에서부터 연산해야 해서 스택을 앞에서 뽑고 넣을 수 있는 함수도 추가해줬다. (pop_front, push_front)

 

여기서 한 가지 주의할 점은, 만약에 스택에 식이 1개 남았다면 그대로 반환해줘야 한다. 3개를 pop해야 연산할 수 있기 때문이다. 

LLI Calculate(void) {
	memset(stack, 0, sizeof(stack));
	top = 0, bot = 0;
	push(oprnd[0]);
	push(oprtr[0]);
	for (int i = 1; i <= N / 2; i++) {
		push(oprnd[i]);
		if (sel[i] == 1) {
			// 3개를 팝해서 계산하기
			LLI a = pop();
			LLI op = pop();
			LLI b = pop();
			push(r_calculate(b, op, a));
		}
		if (i == N / 2) break;
		push(oprtr[i]);
	}

	if (top - bot == 1) return pop(); // 연산자 3개만 들어오면 스택에 하나 남게 됨

	for(int i = 0; i<top; i++){
		LLI a = pop_front();
		LLI op = pop_front();
		LLI b = pop_front();
		LLI res = r_calculate(a, op, b);
		if (top == bot) return res;
		else push_front(res);
	}
	return 0;
}

이 연산 부분이 좀 복잡했다 ㅠㅠ

 

그리고 값들이 최대 2의 31승이기 때문에 int가 아닌 long long int로 자료형 선언을 해줘야 한다!

 

주의할 점

식이 1개만 들어올 경우 그대로 프린트 해줘야 한다 -> 별도 처리 없으면 0출력됨

 

전체 코드

#if 0
#include <stdio.h>
#include <string.h>
#define ADD 7
#define SUB 8
#define MUL 9
#define LLI long long int 

int N;
LLI oprnd[10 + 2];
LLI oprtr[9 + 2];
char str[19+2];
int sel[10 + 2]; // 숫자 앞에 붙일 수 있음
LLI max = 0x7fffffff00000000 * (-1);

void Get_Input(void) {
	int dcnt = 0, rcnt = 0;
	scanf("%d", &N);
	scanf("%s", str);
	for (int i = 0; i < N; i++) {
		if (str[i] >= '0' && str[i] <= '9') oprnd[dcnt++] = (LLI)str[i]-'0';
		else {
			if (str[i] == '+') oprtr[rcnt++] = ADD;
			else if (str[i] == '-') oprtr[rcnt++] = SUB;
			else oprtr[rcnt++] = MUL;
		}
	}
}

void Print_Sel(void) {
	for (int i = 0; i < N / 2+1; i++) {
		printf("%d ", sel[i]);
	}
	printf("\n");
}

LLI stack[100];
LLI top = 0, bot = 0;
void push(LLI c) {
	stack[top++] = c;
}
LLI pop(void) {
	LLI tmp = stack[--top];
	stack[top] = 0;
	return tmp;
}
void push_front(LLI c) {
	stack[--bot] = c;
}
LLI pop_front() {
	LLI tmp = stack[bot++];
	stack[bot-1] = 0;
	return tmp;
}

LLI r_calculate(LLI f, LLI op, LLI s) {
	if (op == ADD) return f + s;
	if (op == SUB) return f - s;
	if (op == MUL) return f * s;
}

LLI Calculate(void) {
	memset(stack, 0, sizeof(stack));
	top = 0, bot = 0;
	push(oprnd[0]);
	push(oprtr[0]);
	for (int i = 1; i <= N / 2; i++) {
		push(oprnd[i]);
		if (sel[i] == 1) {
			// 3개를 팝해서 계산하기
			LLI a = pop();
			LLI op = pop();
			LLI b = pop();
			push(r_calculate(b, op, a));
		}
		if (i == N / 2) break;
		push(oprtr[i]);
	}

	if (top - bot == 1) return pop(); // 연산자 3개만 들어오면 스택에 하나 남게 됨

	for(int i = 0; i<top; i++){
		LLI a = pop_front();
		LLI op = pop_front();
		LLI b = pop_front();
		LLI res = r_calculate(a, op, b);
		if (top == bot) return res;
		else push_front(res);
	}
	return 0;
}

void DFS(int idx) {

	if (idx > N / 2) {
		//Print_Sel();
		LLI res = Calculate();
		if (res > max) max = res;
		return;
	}

	// 재귀
	if((idx==0) || (idx-1 >= 0 && sel[idx-1] != 1)){
		sel[idx] = 1;
		DFS(idx + 1);
	}
	sel[idx] = 0;
	DFS(idx + 1);
}

int main(void) {
	freopen("in.txt", "r", stdin);
	Get_Input();
	if (N == 1) {
		printf("%d", str[0] - '0');
		return 0;
	}
	DFS(1);
	printf("%lld", max);
	return 0;
}

#endif