[백준] 16637 괄호 추가하기 - Java

 

 

문제 출저

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

16637번: 괄호 추가하기

 

 

 

문제 풀이

수식이 주어졌을 때 괄호를 적절히 추가하여 최댓값을 구하는게 이 문제의 요구사항 입니다.

 

저는 DFS로 풀었습니다. 

List<Integer> number를 선언해 수식에 숫자를 순서대로 담았습니다.

List<Character> operation을 선언해 수식에 연산 기호를 순서대로 담았습니다.

 

dfs(int stage, int left)를 선언합니다. stage는 operation 의 순서이고 left는 왼쪽부터 계산한 값 입니다.

처음에는 0과 number.get(0)으로 시작합니다.

연산기호를 계산한 값을 다음 left로 보내는 식으로 값을 탐색하는 겁니다.

이 때, 괄호를 친 경우는 오른쪽에 괄호를 친 수식을 먼저 계산한 다음 left를 계산합니다.

 

 

 

 

소스 코드

package baekjoon.backjoon9.day24;


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

/*
괄호 추가하기
https://www.acmicpc.net/problem/16637
 */

public class B16637 {

    static int n, m;
    static List<Integer> number;
    static List<Character> operation;
    static int answer;

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

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

        number = new ArrayList<>();
        operation = new ArrayList<>();

        String str = br.readLine();


        for(int i = 1; i < n+1; i++) {
            if(i % 2 == 1) {
                number.add(str.charAt(i-1) - '0');
            }
            else {
                operation.add(str.charAt(i-1));
            }
        }

        answer = Integer.MIN_VALUE; // 음수가 나올수도 있다
        dfs(0, number.get(0));
        System.out.println(answer);

    }

    // 연산 순서 정하기
    public static void dfs(int stage, int left) {

        if(stage >= m) {
            answer = Math.max(answer, left);
            return;
        }


        // 그냥 계산한 경우
        int num = calc(left, operation.get(stage), number.get(stage + 1));
        dfs(stage+1, num);

        // 괄호를 친 경우
        if(stage+1 < m) {
            int num1 = calc(number.get(stage+1), operation.get(stage+1), number.get(stage +2));
            int num2 = calc(left, operation.get(stage), num1);
            dfs(stage+2, num2);
        }
    }


    // 사칙 연산
    public static int calc(int num1, char op, int num2) {
        int result = 0;
        if(op == '+') {
            result = num1 + num2;
        }
        else if(op == '-') {
            result = num1 - num2;
        }
        else if(op == '*') {
            result = num1 * num2;
        }

        return result;
    }

}