백준 16637 괄호 추가하기

어떻게 풀어야 할 지는 알겠는데 이를 코드로 어떻게 짜야할지 몰라서 계속 헤매다가 다른 분의 코드를 보고 참고해서 풀었다.

 

처음에는 수식을 입력받은 그대로 두고 이를 통해서 괄호를 넣을 위치를 정하다보니 index를 4칸씩 5칸씩 6칸씩 뛰어다녔다. 그러다보니 코드가 너무 복잡해져서 다른 분의 코드를 참조했고, 수식을 전부다 볼 필요가 없이 연산자를 기준으로 계산을 하면 된다는 것을 알게 되었다.

 

그래서 연산자를 기준으로 다시 풀게 되었다. 하나의 연산자를 기준으로 괄호를 치는 경우와 안치는 경우를 나눠서 풀어야 한다는 것은 알았지만, 이를 코드로 계속 구현하려다 보니 뭔가 안 맞고 엉켰다.

특정 순서의 연산자에서 연산을 할 때, 바로 앞에서 괄호를 쳤는지, 안쳤는지를 구분해서 연산을 하려 했다.

2 * (3 + 4) * 6 => 1

2 * 3 + 4 * 6 => 2

이 두경우를 예로 들 때, 마지막 * 연산자의 차례에 왔을 때

3+4가 괄호로 묶여 있을 경우에는 마지막 6을 곱하면 되지만,

3+4가 괄호로 묶여 있지 않을 경우에는  4 * 6을 괄호로 묶을 수 있기 때문에

이러한 방식으로 풀려고 했다. 그래서 바로 앞 계산을 괄호로 묶었는지를 판별하는 boolean값도 dfs의 인자로 넘겨 주었다.

하지만, 계산이 너무 복잡해졌고, 디버깅이 힘들었다.

 

결국 다시 다른 분의 코드를 참조했다.

현재 연산자를 기준으로 앞 뒤의 피연산자를 계산하여 넘기는(현재 연산자의 피연산자를 괄호로 묶는다) dfs에는 idx를 1만 증가 시켜서 넘겨 주었고,

현재 연산자를 기준으로 뒤, 뒤뒤에 있는 피 연산자를 계산하여 넘기는(현재 연산자의 뒤에 있는 피연산자들을 괄호로 묶고 이 결과를 현재 연산자와 연산한다.) dfs에는 idx를 2 증가 시켜서 넘겨 주었다.

 

이렇게 하면 현재 인덱스의 피연산자들을 괄호를 묶는 경우와 묶지 않는 경우로 간단하게 나눌 수 있다.

코드는 아래와 같다.

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

public class Main {
	static int ans, n;
	static int[] operation;
	static char[] operator;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		operation = new int[n / 2 + 1];
		operator = new char[n / 2];

		int idx1 = 0;
		int idx2 = 0;
		st = new StringTokenizer(br.readLine());
		String token = st.nextToken();
		for (int i = 0; i < token.length(); i++) {
			if (token.charAt(i) == '+' || token.charAt(i) == '-' || token.charAt(i) == '*') {
				operator[idx2++] = token.charAt(i);
			} else {
				operation[idx1++] = Integer.parseInt(token.charAt(i) + "");
			}
		}

		ans = Integer.MIN_VALUE;
		dfs(0, operation[0]);
		System.out.println(ans);
	}

	private static void dfs(int idx, int res) {
		if (idx >= n / 2) {// 모든 연산 다 한 경우
			if (ans < res)
				ans = res;
			return;
		}
		// 현재 idx의 연산자 수행(괄호를 침)
		int ret = cal(res, operator[idx], operation[idx + 1]);
		dfs(idx + 1, ret);

		// 현재 idx의 연산자에 괄호를 치지 않고, 뒤에 연산자가 있을 경우 뒤에 연산자에 괄호를 침
		if (idx + 1 < n / 2) {
			ret = cal(res, operator[idx], cal(operation[idx + 1], operator[idx + 1], operation[idx + 2]));
			dfs(idx + 2, ret);
		}

	}

	private static int cal(int a, char oper, int b) {
		switch (oper) {
		case '+':
			return a + b;
		case '-':
			return a - b;
		case '*':
			return a * b;
		}
		return 0;
	}

}