[백준] code.plus(브루트 포스 Part 1,JAVA)16637번, 괄호 추가하기

문제 링크

16637번: 괄호 추가하기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 중첩된 괄호는 사용할 수 없습니다.

2. 수식에 괄호를 적절히 사용하여 얻을 수 있는 최대값을 결과로 출력합니다.

3. 연산자 우선순위는 모두 동일합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 수식에 괄호를 놓는 모든 경우를 놓아서 결과를 계산합니다.

 

3. 계산한 값 중 가장 큰 값을 결과로 출력합니다.

 

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 9수식 : 3 + 8 * 7 - 9 * 2

 

2. 수식에 괄호를 놓는 모든 경우를 놓아서 결과를 계산합니다.

 

3 + 8 * 7 - 9 * 2 : 136

3 + (8 * 7) - 9 * 2 : 100

3 + 8 * (7 - 9) * 2 : -44

3 + (8 * 7) - (9 * 2) : 41

3 + 8 * 7 - (9 * 2) : 59

 

3. 계산한 값 중 가장 큰 값을 결과로 출력합니다.

 

가장 큰 값 136을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• dfs을 실행하여 수식에 괄호를 놓는 모든 경우에 최대값을 구해서 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs함수는 수식에 괄호를 놓을 수 있는 모든 경우를 탐색하여 최대값을 구합니다.
• cal함수는 연산자에 따른 값들을 계산합니다.

 

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

public class Main {
    static int N, answer = Integer.MIN_VALUE;
    static ArrayList<Integer> num = new ArrayList<>();	//수식 숫자 저장 리스트
    static ArrayList<Character> operation = new ArrayList<>();	//수식 연산자 저장 리스트
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        //수식 정보 저장
        for(int i=0;i<N;i++){
            if(i%2==0)
                num.add(Character.getNumericValue(str.charAt(i)));
            else
                operation.add(str.charAt(i));
        }
        dfs(num.get(0), 0);	//괄호 놓는 모든 경우 탐색 및 최대값 구하기
        bw.write(answer + "");	//최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //수식에 괄호를 놓는 모든 경우 탐색하는 함수
    static void dfs(int value, int index){
        //수식 완성시!
        if(index == operation.size()){
            answer = Math.max(answer, value);
            return;
        }
        //괄호 놓지 않기
        int temp = cal(value, operation.get(index), num.get(index+1));
        dfs(temp, index+1);
        
        //괄호 놓기
        if(index+1 < operation.size()){
            temp = cal(value, operation.get(index), cal(num.get(index+1), operation.get(index+1), num.get(index+2)));
            dfs(temp, index+2);
        }
    }
    //연산자에 따른 값 계산 함수
    static int cal(int n1, char operation, int n2){
        if(operation == '+')
            return n1 + n2;
        else if(operation == '-')
            return n1 - n2;
        else
            return n1 * n2;
    }
}