[JAVA] BOJ(백준) - 괄호 추가하기 - 16637

문제내용

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

16637번: 괄호 추가하기

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

---

문제풀이

당연하지만 이 문제는 2가지의 경우의수로 나워서 풀어내면 된다.

1. 괄호가 없을때

2. 괄호가 있을때

 

문제는 이걸 어떻게 구현하냐 하는건데... 사실 이부분은 필자도 다른분 블로그를 참조했다.. DFS에 대한 구현 능력이 부족한듯 ㅠ

아무튼 먼저 DFS로 괄호 없을때의 합을 구해준다. 이후에 모든 연산자와 수를 다사용 했을때 뒤에서부터 괄호를 치면서 경우의수를 더해준다. 이말이 무슨 말이냐면

 

"3+8*7-9*2" 라는 수식이 있다고 할때,

char[] oper = { +, * , - ,* } , int[] nums = { 3, 8, 7, 9, 2 } 로 나눌수 있다. 이를 이용하면

 

1. 괄호가 없을경우

sum=3에서 시작 ---->

sum = 3+8 -> DFS -> sum = 11*7 -> DFS -> sum = 77-9 -> DFS -> sum = 68*2 -> DFS -> sum=136

이 된다. 즉, 재귀를 통해 하나씩 sum값을 수식대로 계산해나간다.

 

2. 괄호가 있을경우

괄호가 있을땐 sum=77에서 시작한다. 즉, "3+8*7" 까지는 계산돼 있고 여기서 시작한다는 것.

sum = 77-(9*2) = 59 -> DFS return -> sum = 11 * (7-9) * 2 -> DFS return -> ... sum = 3 + (8*7) - 9 * 2

가된다.

 

한마디로 왼쪽에 먼저 계산된걸 sum에 두고, 오른쪽에 괄호를 치면서 계산된 괄호값을 sum과 다시 계산하는 방식이다.

 

사실 DFS는 코드를 보고 이해하는게 좋고, 코드를 보고 디버깅하면서 이를 이해하려면

자바의 경우 재귀함수는 재귀할 때마다 Stack메모리 공간에 쌓인다는걸 알아둬야한다. 그래서 LIFO 방식으로 재귀 함수가 처리된다는걸 알고 있어야 이해하기 편하다는걸 참고하자.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int max = Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		char[] sick = br.readLine().toCharArray();
		char[] oper = new char[n/2];
		int[] nums = new int[n/2+1];
		
		int operIdx=0, numIdx=0; 
		for(int i=0; i<sick.length; i++) {
			char ch = sick[i];
			if(ch=='+' || ch=='-' || ch=='*') oper[operIdx++] = ch;
			else nums[numIdx++] = ch-'0';
		}
		
		dfs(nums[0],0,nums,oper);
		System.out.println(max);
	}
	
	public static void dfs(int sum, int idx, int[] nums, char[] oper) {
		if(idx>=oper.length) {//연산자 다썼으면 최댓값 갱신.
			max = Math.max(max, sum);
			return;
		}
		
		//괄호 없는경우
		int res = cal(oper[idx], sum, nums[idx+1]);//왼쪽부터 계산
		dfs(res, idx+1, nums, oper);
		
		//괄호 있는경우(위에서 dfs함수가 끝나고 들어와지기 때문에 idx는 오른쪽 부터임)
		if(idx+1<oper.length) {
			int res1 = cal(oper[idx+1], nums[idx+1], nums[idx+2]);//오른쪽에 괄호친거 계산
			dfs(cal(oper[idx],sum,res1), idx+2, nums, oper);//지금까지 왼쪽의 sum값과 괄호친값을 계산하고 재귀 ㄲ
			//이때 재귀할때는 괄호친곳까지 계산된값이 sum이되고 그 뒤부터 다시 계산한다는 말임.
		}
	}
	
	public static int cal(char op, int n1, int n2) {
		if(op=='+') return n1+n2;
		else if(op=='-') return n1-n2;
		else return n1*n2;
	}
}

---

마치며

DFS+백트래킹을 이용한 완전탐색 문제다. 근데 이번문제로 체감된게 DFS에 대한 구현능력이 좀 부족하다는걸 느꼈다..

그래서 당분간은 DFS를 활용하는 완전탐색 문제를 주로 풀 생각이다.