[백준] 16637: 괄호 추가하기 (DFS Brute-force) - JAVA

삼성 A형 기출문제

https://www.acmicpc.net/problem/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은 홀수이다.

19
1-9-1-9-1-9-1-9-1-9

 

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

24

 

 

# 필요개념

처음 문제를 봤을 때 이게 왜 골드문제일까 싶었다. 그냥 무한 if문으로 풀 수 있을 거라고 생각했기 때문이다.

실제로 그렇게 문제 속 예제를 모두 맞혔는데, 제출하고 보니 생각보다 반례가 많았다.

• 현재 부호가 곱셈인 경우
  • 다음 부호가 덧셈이면 그 연산 먼저 한 후 현재 곱셈을 해야 값이 더 커진다
  • 다음 부호가 뺄셈이면 그냥 현재 연산을 먼저 하는게 낫다 생각했는데, 앞에서 연산해온 누적값이 음수이고 뒷 연산을 한 결과도 음수면 뒷연산 먼저 해서 음수 * 음수로 양수를 만드는 게 낫다
• 현재 부호가 뺄셈인 경우
  • 다음부호가 뺄셈이면 다음 연산을 해보고, 그 값이 음수면 그 연산을 먼저 하는게 낫다. -(-a) = a 로 만들 수 있기 때문에!

... 등등등등!!! 생각보다 경우의 수가 너무 많아서 이걸 다 나누기는 결코 쉽지 않다고 판단했다. 그래서 DFS를 사용해 모든 경우를 탐색하자! 로 전략을 변경했다.

 

나는 연산자의 위치를 기준으로 앞에서 누적한 연산 결과를 prev 변수에 넣었다. 현재 연산자가 마지막 연산자라면 이거만 재귀로 처리하고, 마지막 연산자가 아니면 뒷 연산을 먼저 한 경우까지 계산해 재귀 처리를 진행했다.

+, -, *를 if문으로 처리하니 코드가 매우 난잡해져서, 별도의 apply 함수로 분리해 처리했다.

 

재귀의 종료조건은 현 인덱스가 N을 넘어서는 경우로 지정하고, 그때 ans를 최댓값으로 갱신하는 방식을 택했다.

dfs 종료조건

 

아래가 핵심 로직이라고 할 수 있다.

 

다행스럽게도 N의 크기가 작아서 brute-force로 처리가 가능했다!

 

# Code

리팩토링 전 코드

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


// 16637
public class Main {
    static String comp = "";

    static int N;
    static long ans = Long.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        comp = br.readLine();
        comp(1, comp.charAt(0) - '0');
        System.out.println(ans);
    }

    private static void comp(int idx, long prev) {
        if (idx >= N) {
            ans = Math.max(ans, prev);
            return;
        }

        String op = String.valueOf(comp.charAt(idx));
        long next = 0;
        if (idx + 2 < N) {
            String nextOp = String.valueOf(comp.charAt(idx + 2));
            if (nextOp.equals("+")) next = (comp.charAt(idx + 1) - '0') + (comp.charAt(idx + 3) - '0');
            else if (nextOp.equals("-")) next = (comp.charAt(idx + 1) - '0') - (comp.charAt(idx + 3) - '0');
            else next = (comp.charAt(idx + 1) - '0') * (comp.charAt(idx + 3) - '0');

            if (op.equals("+")) {
                comp(idx + 4, prev + next);
            } else if (op.equals("-")) {
                comp(idx + 4, prev - next);
            } else {
                comp(idx + 4, prev * next);
            }
        }
        if (op.equals("+")) {
            comp(idx + 2, prev + (comp.charAt(idx + 1) - '0'));
        } else if (op.equals("-")) {
            comp(idx + 2, prev - (comp.charAt(idx + 1) - '0'));
        } else {
            comp(idx + 2, prev * (comp.charAt(idx + 1) - '0'));
        }
    }
}

 

리팩토링 후 최종코드

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

// 16637
public class Main {
    static String comp = "";
    static int N;
    static long ans = Long.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        comp = br.readLine();
        comp(1, comp.charAt(0) - '0');
        System.out.println(ans);
    }

    private static void comp(int idx, long prev) {
        if (idx >= N) {
            ans = Math.max(ans, prev);
            return;
        }
        char op = comp.charAt(idx);
        comp(idx + 2, apply(prev, op, comp.charAt(idx + 1) - '0'));
        if (idx + 2 < N) {
            char nextOp = comp.charAt(idx + 2);
            long next = apply(comp.charAt(idx + 1) - '0', nextOp, comp.charAt(idx + 3) - '0');
            comp(idx + 4, apply(prev, op, next));
        }
    }

    private static long apply(long a, char op, long b) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        return a * b;
    }
}

 

 

# 결과