16637번: 괄호 추가하기

문제

길이가 N인 수식이 주어집니다. 수식은 0부터 9까지의 정수와 연산자(+, -, ×)로 이루어져 있습니다. 연산자 우선순위는 모두 동일하며, 왼쪽에서부터 순서대로 계산해야 합니다. 수식에 괄호를 추가하면 괄호 안의 식을 먼저 계산할 수 있습니다. 단, 괄호 안에는 연산자가 하나만 들어있어야 하며, 중첩된 괄호는 사용할 수 없습니다. 괄호를 적절히 추가하여 얻을 수 있는 결과의 최댓값을 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 수식의 길이 N (1 ≤ N ≤ 19)이 주어집니다. 둘째 줄에는 수식이 주어집니다.
• 출력: 첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력합니다.

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

풀이: 백트래킹(DFS)을 활용한 모든 경우의 수 탐색

수식의 길이가 최대 19이므로, 연산자의 개수는 최대 9개입니다. 각 연산자에 대해 괄호를 묶을지 말지를 결정하는 모든 경우의 수를 탐색하는 백트래킹(DFS) 방식을 사용합니다.

• 상태 전달 (go 메서드): idx는 현재 탐색 중인 숫자의 인덱스를, sum은 이전까지 연산이 완료된 누적 결괏값을 의미합니다. 초기 호출은 첫 번째 숫자(idx = 2, sum = s.charAt(0) - '0')부터 시작합니다.
• 경우의 수 1: 괄호를 추가하지 않는 경우 현재 연산자(s.charAt(idx - 1))를 사용하여 이전까지의 누적값(sum)과 현재 숫자(s.charAt(idx))를 바로 연산합니다. 그 결과를 다음 재귀로 넘기며 인덱스를 2 증가시킵니다. (idx + 2)
• 경우의 수 2: 괄호를 추가하는 경우 현재 숫자(s.charAt(idx))와 다음 숫자(s.charAt(idx + 2))를 다음 연산자(s.charAt(idx + 1))로 먼저 묶어서 계산합니다. 그 후, 이전 누적값(sum)과 방금 괄호로 계산한 결과를 현재 연산자(s.charAt(idx - 1))로 연산하여 다음 재귀로 넘깁니다. 숫자 2개를 한 번에 처리했으므로 인덱스는 4 증가시킵니다. (idx + 4)
• 최댓값 갱신: 인덱스가 배열의 범위를 벗어나게 되면(idx >= n) 수식의 끝에 도달한 것이므로, 계산된 sum으로 전체 최댓값 ans를 갱신합니다. (초깃값을 Integer.MIN_VALUE로 설정하여 음수 결과에도 대비합니다.)

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static String s;
    static int ans = Integer.MIN_VALUE;

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

       n = Integer.parseInt(br.readLine());
       s = br.readLine();

       go(2, s.charAt(0) - '0');

       bw.write(ans + "");

       bw.flush();
    }

    static void go(int idx, int sum) {
       if (idx >= n) {
          ans = Math.max(ans, sum);
          return;
       }

       // 1. 괄호를 치지 않고 바로 순서대로 연산하는 경우
       go(idx + 2, eval(sum, s.charAt(idx) - '0', s.charAt(idx - 1)));
       
       // 2. 괄호를 쳐서 뒤의 두 숫자를 먼저 연산한 후 누적값과 연산하는 경우
       if (idx + 2 < n) {
          go(idx + 4,
             eval(sum, eval(s.charAt(idx) - '0', s.charAt(idx + 2) - '0', s.charAt(idx + 1)), s.charAt(idx - 1)));
       }
    }

    static int eval(int n1, int n2, char op) {
       if (op == '+')
          return n1 + n2;
       else if (op == '-')
          return n1 - n2;
       return n1 * n2;
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force), 백트래킹 (Backtracking)