[JAVA] 16637 - 괄호 추가하기 💛3: 방향이 있는 그래프(DAG)에서의 완전탐색은 자신있게 구현하자!

들어가며

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

 

문제는 직관적으로 이해가 가능하다. 주어진 수식에 괄호를 추가하여 연산의 우선순위를 바꿀 수 있는데, 그 경우의 수에서 최소가 되는 경우를 답으로 출력하면 되는 문제다. 근데 사실 문제 이해만 되고,, 로직이 막 떠오르진 않았다. 마음을 다잡고 가보자!

본문으로

연산은 왼쪽에서부터 순서대로 계산이 되기 때문에 방향이 있는 그래프(DAG)임을 알 수 있다. 그리고 괄호를 어떻게 치냐에 따라서 정답이 다 달라지기 때문에 다 돌아봐야하는 완전탐색 문제도 쉽게 눈치를 챌 수 있다. 다행이 수식의 길이는 19가 최대이기에 시간복잡도가 그렇게 걱정되지도 않는다. 정도로 문제 분석을 끝나고 아래 정답 코드를 보자.

public class Main {
    static List<String> oper;
    static List<Integer> nums;
    static int ret;
    static int operLength;

    static int cal(int a, int b, String oper) {
        if (oper.equals("+")) {
            return a + b;
        } else if (oper.equals("-")) {
            return a - b;
        }
        return a * b;

    }

    static void go(int idx, int value) {
        if (idx == operLength) {
            ret = Math.max(value, ret);
            return;
        }

        go(idx + 1, cal(value, nums.get(idx + 1), oper.get(idx)));

        if (idx + 1 < operLength) { // 다음 연산자가 존재해야 다음거를 미리 계산하지! -> 괄호를 만들 수 있나 확인
            int nextValue = cal(nums.get(idx + 1), nums.get(idx + 2), oper.get(idx + 1));
            go(idx + 2, cal(value, nextValue, oper.get(idx)));
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        oper = new ArrayList<>();
        nums = new ArrayList<>();

        String[] inputs = bf.readLine().split("");
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                nums.add(Integer.parseInt(inputs[i]));
            } else {
                oper.add(inputs[i]);
            }
        }
        ret = Integer.MIN_VALUE;
        operLength = (N + 1) / 2 - 1;
        go(0, nums.get(0));

        System.out.println(ret);
    }
}

---

모두 다 돌아야하기에 핵심로직은 아래와 같이 재귀적으로 구성된다. 재귀의 종료조건도 idx == operLegth 즉 마지막 계산일때의 값을 비교하여 정답을 계속 최신화 시켜주었다. 괄호 안치고 그냥 옆에것과 계산하는 경우와 다음것에 괄호치고 연산의 우선순위를 바꾸는 것만 계속 재귀적으로 이어가게끔 설계해주면 된다.

    static void go(int idx, int value) {
        if (idx == operLength) {
            ret = Math.max(value, ret);
            return;
        }
		// 1. 괄호 안치고 바로 다음 값과 계산
        go(idx + 1, cal(value, nums.get(idx + 1), oper.get(idx)));

		// 2. 다음 것에 괄호치고 계산하는 경우는 다음거 미리 계산 후 이번거 계산
        if (idx + 1 < operLength) { // 다음 연산자가 존재해야 다음거를 미리 계산하지! -> 괄호를 만들 수 있나 확인
            int nextValue = cal(nums.get(idx + 1), nums.get(idx + 2), oper.get(idx + 1));
            go(idx + 2, cal(value, nextValue, oper.get(idx)));
        }

    }

주석에 친절하게 적어놓긴 했지만, 이러한 재귀적 완탐 흐름의 로직이 참 떠오르기 힘든 것 같다. 많은 연습이 필요할 듯 하다.

먼저 어떠한 경우로 나눠지는지 찾고(여기선 괄호를 쳤는지 안쳤는지 두가지밖에 없지만, 10가지가 넘어갈 수도 있다고 한다..) 그것을 재귀적으로 잘 가게끔 인덱스를 잘 설정해주는 것이 중요할 듯 하다.

마무리하며

요즘 완전탐색 문제들을 자주 풀어보는 중인데, 확실히 문제를 정확히 이해하고 그것을 다 돌기 위해 재귀적으로 설계하는 것은 오로지 연습만이 답인 것 같다. 앞으로도 꾸준히 풀어보자~!