백준 16639 괄호 추가하기 3 java

DP DFS

전수민

Nov 23, 2025

TABLE OF CONTENTS

1. 문제에 대하여 📦

문제 링크: https://www.acmicpc.net/problem/16639
주어진 연산식에 괄호를 적절하게 추가하여서 나올 수 있는 최대값을 출력해라.

2. 코드가 나오기까지 🛠️

*KEY WORD: DP, DFS

(1) TOP-DOWN의 원리

주어진 연산식을 풀어가며 중간 결과를 합쳐갔을 때, 최종적으로 풀어야하는 연산식은 위 3가지 중 하나이다. 우리는'최종 연산에서 그 내부 과정으로 점점 세분화하여 내려가는 TOP-DOWN 방식'으로 문제를 풀 것이다. 이를 위해 재귀를 활용한다.

이때 주의해야할 점은 연산자의 위치를 계속 변동해가면서 모든 경우의 수를 확인해야 한다는 것이다.

위와 같이 주어진 전체 범위 내에서 a와 b의 범위를 달리하며 모든 경우의 수를 확인하고 그 중 최대값 혹은 최소값을 구해서 이전 깊이의 재귀로 돌아가야한다.

(2) 구해야할 경우의 수

A. 덧셈, 뺄셈의 경우

재귀의 깊이를 한 단계 깊게 표현하면 다음과 같을 것이다. ans가 최대값이 되기 위해서 각 b와 c는 어떤 값이 나와야 하는가?

b와 c 외부 연산자가 + 이면 b와c 사이의 최대값을, -이면 최소값을 뽑아내야 한다.

모든 경우를 풀어 쓰면 다음과 같다.

a + (b+c)의 경우 b,c 모두 최대값이 되어야 ans가 최대값이 될 것이다.

a + (b-c)의 경우는 b는 최대값, c = 최소값이 되어야 ans가 최대값이 될 것이다.

a-(b+c)는 b,c 모두 최소값이 되어야 ans의 최대값을 구할 수 있다.

a-(b-c)는 b는 최소값, c는 최대값이 되어야 ans의 최대값을 구할 수 있다.

b와 c의 연산 결과를 z라고 쳤을 때, 해당 z의 최대값과 최소값이 모두 필요함을 알 수 있다. 이를 표현하기 위해 3차원 배열을 활용한다. 각 행렬의 값은 다음과 같다.


dp [최대, 최소를 나타내는 플래그][연산식 시작 위치][연산식 끝 위치]

dp[0][b][c] = b와 c 연산의 최대값
dp[1][b][c] = b와 c 연산의 최소값
dp[0][a][c] = a와 c 연산의 최대값 (위의 식에서는 전체 연산의 최대값이 된다.)

B. 곱셈의 경우

덧셈과 뺄셈을 구할 때, 중간 연산 구간에서 나올 수 있는 최대값 혹은 최소값을 모두 구하는 식으로 풀었다. 하지만 곱셈의 경우, 음수x음수 가 최대값이 되는 경우도 있으므로, 최대 최소만 구해서는 어느 쪽이 미래에 최대값을 보장하는지 알 수가 없다. 따라서 곱셈 계산 시에는 밑의 4가지 경우를 모두 확인해봐야 한다.

(3) 캐싱

세분화해서 중간 계산 결과를 구하다보면, 중복되는 중간 계산 결과가 필요할 수 있다. 이를 대비해서 dp 배열을 만들어서 최초 계산 시 저장한 뒤, 추후 필요할 떄는 이를 꺼내 쓰는 식으로 구현한다. 이는 재귀 깊이와 넓이를 3차원 배열의 크기 만큼 줄인다.

(4) 시간복잡도 분석 ⏳

재귀를 사용하기는 하지만, 3차원 배열 전체를 채울때까지만 반복하므로 최종 시간복잡도는 다음과 같다.
주어진 문자열의 길이가 N일 떄, 그 중 피연산자의 개수는 N/2 이다. 따라서

O((\frac{N}{2})^3)

3. 코드 🌐

(1) SUDO CODE 💬


0. 초기화 - 연산자, 피연산자 옮겨 담기
1. dfs를 전체 범위로 잡고 다음을 반복
   (인수= 구해야하는 값이 최대값인지 최소값인지-이전 재귀에서 결정, 시작구간, 끝구간)

   (1) 주어진 전체 구간에서 A와 B의 범위 정하기 A (연산자) B
	 (2) 인수로 주어진 최대값, 최소값에 따라 현 구간의 최대값 or 최소값 구하기
	 (3) DP에 해당 결과를 넣고, 탈출
	 (4) start == end, 혹은 구하고자 하는 DP 구간이 이미 구해진 경우 바로 탈출 로직 넣기

(2) JAVA CODE ☕


import java.util.*;
import java.io.*;
 // b 17255 N으로 만들기
public class Main {
    static int N;
    static int [] nums;
    static char [] oper;
    static int [][][] dp; // [최대,최소 플래그][시작 위치][끝 위치]
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int [2][N][N];
        nums = new int [N/2 + 1];
        oper = new char [N/2];
        String row = br.readLine();
        for(int i = 0; i < N; i++){
            if(i%2 == 0) nums[i/2] = row.charAt(i) - '0';
            else oper[i/2] = row.charAt(i);
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                dp[0][i][j] = Integer.MIN_VALUE;
                dp[1][i][j] = Integer.MAX_VALUE;
            }        }        System.out.printf("%d", dfs(0, 0, N/2));

//        for(int i = 0; i < N; i++){
//            for(int j = 0; j < N; j++){
//                System.out.printf("최대: %d, 최소: %d", dp[0][i][j], dp[1][i][j]);
//            }
//            System.out.println();
//        }
    }

    public static int dfs (int flag, int start, int end){ // flag는 현재 위치에서 해당 값이 최대가 되어야 하는지, 최소가 되어야 하는지
        if(start == end) {
            dp[flag][start][end] = nums[start];
            return dp[flag][start][end];
        }        if((flag == 0 && dp[flag][start][end] != Integer.MIN_VALUE)
            || (flag == 1 && dp[flag][start][end] != Integer.MAX_VALUE)){
            return dp[flag][start][end];
        }        int temp_value = flag==0? Integer.MIN_VALUE : Integer.MAX_VALUE;
        for (int i = start; i < end; i++) {
            switch (oper[i]){
                case '-': {
                    if(flag == 0) temp_value = Math.max(temp_value, dfs(0, start, i) - dfs(1, i+1, end));
                    else temp_value = Math.min(temp_value, dfs(1, start, i) - dfs(0, i+1, end));
                    break;
                }                case '+': {
                    if(flag == 0) temp_value = Math.max(temp_value, dfs(0,start,i) + dfs(0,i+1, end));
                    else temp_value = Math.min(temp_value, dfs(1,start,i) + dfs(1, i+1, end));
                    break;
                }                case '*': {
                    if(flag == 0) temp_value = Math.max(temp_value,
                        Math.max(dfs(0,start,i)*dfs(0,i+1, end),
                            Math.max(dfs(1, start, i)*dfs(1, i+1, end),
                                Math.max(dfs(0,start,i)*dfs(1,i+1, end), dfs(1, start, i)*dfs(0,i+1,end)))));
                    else temp_value = Math.min(temp_value,
                        Math.min(dfs(0,start,i)*dfs(0,i+1, end),
                            Math.min(dfs(1, start, i)*dfs(1, i+1, end),
                                Math.min(dfs(0,start,i)*dfs(1,i+1, end), dfs(1, start, i)*dfs(0,i+1,end)))));
                    break;
                }            }        }        dp[flag][start][end] = temp_value;
        return dp[flag][start][end];
    }
 }