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

1. 문제 링크

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

16637번: 괄호 추가하기

 

2. 접근법

1.

입력받은 수식을 수와 연산자로 나누어 주었다.

numbers 리스트에는 수, operators 리스트에는 연산자

 

2.

dfs 탐색으로 계산 결과(result)와 어디까지 계산했는지 인덱스(index)를 넘겨주며 괄호는 치는 경우를 나누어갔다.

 

3.

괄호는 치는 경우는 다음과 같이 구분했다.

 

3 + 8 * 7 - 9 * 2 인 경우,

3 + 8 * 7 을 다음과 같이 두 가지 경우로 나눌 수 있다.

 

(3 + 8) * 7

3 + (8 * 7)

 

첫 번째 경우, (3 + 8) 계산을 한 후 calculated에 담고 수 8까지 계산했으므로 index + 1을 넘겨준다.

dfs(calculated, index + 1)

 

두 번째 경우, (8 * 7) 계산한 후, 3 + 56 을 계산한 후 calculated에 담고, 수 7까지 계산했으므로 index + 2를 넘겨준다.

dfs(calculated, index + 2)

 

4.

계산은 calculate() 함수를 구현해 사용했다.

 

5. 

그렇게 dfs 탐색을 하며 마지막 인덱스인 경우, 더 이상 계산할 게 남지 않았으므로

최댓값을 담는 ans 변수를 result로 업데이트해주었다.

 

3. 코드

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

// 괄호 추가하기

public class BJ16637 {

    static int n;
    static int ans = Integer.MIN_VALUE;
    static ArrayList<Integer> numbers = new ArrayList<>();
    static ArrayList<Character> operators = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        String line = br.readLine();
        for(int i = 0; i < n; i++) {
            if(i % 2 == 0) {
                numbers.add(line.charAt(i) - '0');
            }
            else {
                operators.add(line.charAt(i));
            }
        }

        dfs(numbers.get(0), 0);
        System.out.println(ans);
    }

    private static void dfs(int result, int index) {

        if(index == numbers.size() - 1) {
            ans = Integer.max(ans, result);
            return;
        }

        // (a ? b) ? c 연산인 경우, (a ? b) 계산하기
        int calculated = calculate(result, numbers.get(index + 1), operators.get(index));
        dfs(calculated, index + 1);

        // a ? (b ? c) 연산인 경우, a ? (b ? c) 계산하기
        if(index + 2 < numbers.size()) {
            calculated = calculate(result, calculate(numbers.get(index + 1), numbers.get(index + 2), operators.get(index + 1)), operators.get(index));
            dfs(calculated, index + 2);
        }
    }

    private static int calculate(int a, int b, char op) {

        switch(op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
        }
        
        return 0;
    }

    
}

 

4. 막힌 부분

어떻게 풀어야 될지 감이 안 와서 고민 좀 하다 구글링을 했다.

그래서 DFS 탐색인 걸 알고 풀었다.

 

처음에는

(a ? b) ? c 연산인 경우, (a ? b) ? c 까지 계산한 후

dfs()로 넘겼다.

 

예제 입력 6에서 막혔는데,

(a ? b) ? (c ? d) ? (e ? f) ... 인 경우를 탐색하지 못하기 때문이다.

 

그래서

(a ? b) ? c 연산인 경우, (a ? b) 까지만 계산한 후

c부터 다시 괄호 치는 경우를 나눠줘야, 즉 c부터 다시 dfs() 탐색을 들어가야 모든 경우를 구할 수 있었다.