[BOJ] 16637 괄호추가하기 [Java]

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

16637번: 괄호 추가하기

---

1. 문제요약

길이가 N인 수식에서 숫자 2개, 연산자 1개만 괄호로 묶을 수 있고, 괄호는 여러개 사용할 수 있다.

계산한 결과 중 최대값을 출력하는 문제이다.

여기서, N은 항상 홀수이며, 괄호를 추가하지 않아도 된다. 

 

2. 풀이

모든 경우를 탐색한 후, 매번 최대값을 갱신해주는 방식으로 하기 위해 백트래킹을 사용하였다.

모든 경우라함은,

지금 위치에서 괄호를 묶지 않고 식의 끝까지 계산했을 경우,

지금 위치에서 괄호를 묶고 식의 끝까지 계산했을 경우이다. 

 

1. N은 홀수 고정이므로 수식의 짝수자리에는 숫자, 홀수자리에는 연산자가 무조건 올 것이다.

짝수자리면 숫자 ArrayList, 홀수자리면 연산자 ArrayList에 각각 넣어줬다.

 

2. 또, 연산자 우선순위 없이 왼쪽부터 차례대로 계산하므로 calc 함수를 따로 만들어줘서 연산자, 양 옆 숫자를 파라미터로 받아 calc 안에서 연산하고 결과를 return했다.

주의할 점은 인덱스이다. 여기서 헷갈렸는데,

맨 처음 sum은 맨 앞 숫자로 넣어주고 시작했다. 그럼 맨 앞 숫자는 괄호를 칠 수 없지 않을까?라고 생각했는데,

이건 고려해줄 필요가 없었다.

어차피 연산은 왼쪽부터 시작이다. 괄호를 묶지 않는 재귀함수를 호출하면, 맨 처음 숫자와 그 다음 숫자가 계산된다.

즉, 이 둘을 괄호로 묶은거나 마찬가지다. 

 

3. 괄호 안했을 경우 재귀함수 호출, 괄호 했을 경우 재귀함수 호출 두 가지로 나뉜다.

기저조건은 지금 숫자/연산자가 인덱스 범위를 넘어갔을 경우, max 갱신 후 return 해주었다.

 

내가 놓친 부분은 정답은 2^31보다 작고, -2^31보다 크다. 이 부분이다.

2^31 = 2147483648 이다. 즉, 최대값이 될 수 있는 범위는 -2147482648 < max < 2147482648

어디서 많이 본 숫자다. 바로 int 범위와 비슷하다.

나는 처음에 max = 0으로 초기화해줬다. 그래서 제출하면 항상 틀렸다고 떴다.. 

최대값으로 -2147483647이 나올 수도 있다. 따라서 max = 0이 아닌 max = -2147483648로 설정해줘야 한다.

max = Integer.MIN_VALUE; 로 하니까 맞았다.

 

3. 문제점

왜 틀렸는지 고민할 때 범위가 문제가 되는가.. 싶어서 분명 저 문구를 봤다

'정답은 2^31보다 작고, -2^31보다 크다.'

정답이라고 적혀있어서 최대값의 범위라고 생각못하고 지나쳤다. 

테스트케이스는 다 맞는데 틀렸다고 뜰 경우, 범위를 보고 또 보자..

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class 괄호추가하기 {

	static int N, max;
	static String sik;
	static List<Character> op = new ArrayList<>();
	static List<Integer> num = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		sik = br.readLine();
		for (int i = 0; i < sik.length(); i++) {
			if (i % 2 == 0)
				num.add(sik.charAt(i) - '0');
			else
				op.add(sik.charAt(i));
		}

		max = Integer.MIN_VALUE;
		dfs(num.get(0), 0, 1);
		System.out.println(max);
	}

	static void dfs(int sum, int opIdx, int numIdx) {
		if (numIdx >= num.size() || opIdx >= op.size()) {
			max = Math.max(max, sum);
			return;
		}

		// 괄호X
		int res1 = calc(sum, op.get(opIdx), num.get(numIdx));
		dfs(res1, opIdx + 1, numIdx + 1);
		
		// 괄호O
		if (numIdx+1 < num.size()) {
			int res2 = calc(sum, op.get(opIdx), calc(num.get(numIdx), op.get(opIdx + 1), num.get(numIdx + 1)));
			dfs(res2, opIdx + 2, numIdx + 2);
		}

	}

	static int calc(int num1, char oper, int num2) { // 연산 우선순위 없앰
		switch (oper) {
		case '+':
			return num1 + num2;
		case '-':
			return num1 - num2;
		case '*':
			return num1 * num2;
		}
		return 1;
	}
}