백준 16637번) 괄호 추가하기(JAVA)

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

16637번: 괄호 추가하기

 

#문제

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

 

#알고리즘

완전탐색

 

 

#풀이방법

완전 탐색이지만 문제에서 설명하고 있는 것들을 어떻게 구현해야 하는지 오랜 시간이 걸렸다... 조합과 백트래킹으로 접근하려고 하다보니 머리만 쥐어뜨고 오랜 시간이 걸렸다. 구글링을 하다보니 dfs로 괄호를 치지 x, 괄호를 친다 이 2가지로

나뉘어 끝에 도달할 경우, 비교하여 정답을 도출해내는 코드를 보고 저거다!!! 라고 외치며, 코드를 짜기 시작했다....

 

for(int i=0; i<str.length(); i++) {
            
            if(i % 2 == 0) {
                num.add(str.charAt(i)-'0');//숫자 list
            }
            else {
                op.add(str.charAt(i));//연산자 list
            }
            
        }

 

Arraylist를 2개 선언하여 op과 num을 따로 구분하여 넣는다. String으로 입력을 받으므로, 짝수인 경우 숫자이므로 num에 넣고, 홀수인 경우 연산자이므로 op에 넣는다.

 

public static void dfs(int depth,int n) {
        
        if(depth >= op.size()) {
            
            if(n > max)
                max = n;
            
            return;
        }//끝에 도달했다면 max와 비교한 후, return
        
        dfs(depth+1 , cal(n, op.get(depth) , num.get(depth+1)));
        //1.괄호 x -> 단순 계산
        
        if(depth+2 < num.size()) {
            
            dfs(depth+2 , cal(n, op.get(depth) , cal(num.get(depth+1) , op.get(depth+1) , num.get(depth+2))));
            
            // 앞에 수식을 미리 계산하여 지금 숫자와 계산한다.
            // 앞에 수식을 미리 계산하기 때문에 괄호가 없는 depth+1와 다르게 depth+2로 다음 함수를 호출한다.
            
        }//if문을 사용하여 범위 내에 있는지 먼저 확인 
        //2. 괄호 o
        
    }

 

dfs로 재귀함수를 이용하여, 괄호를 친것과 괄호를 치지 않는 것 이 2가지로 나누어 함수를 호출하고,

 

if문을 사용하여 괄호나 숫자 범위 안에 있는지를 먼저 체크 

 

1. 괄호가 없는 경우

-> 괄호가 없는 경우는 지금 있는 숫자 위치와 다음 숫자 위치를 계산해서 재귀 함수로 호출하면 된다.

 

2. 괄호가 있는 경우

-> 괄호가 있는 경우는 범위를 초과할 킹능성이 있기 때문에 앞에서 말했듯이 if문을 써서 범위

안에 있는지 확인 후, 앞에 있는 수식을 먼저 계산하여 지금 수식과 계산하고 depth+2로 다음 것을 건너뛴다.

 

 

#전체 코드

 

import java.util.*;
//3t
 
public class Main {
 
    static int max = Integer.MIN_VALUE;
    static char[] exp;
    static int N;
    
    static ArrayList<Integer> num = new ArrayList<>();
    //숫자
    static ArrayList<Character> op = new ArrayList<>();
    //연산자
    
    public static int cal(Integer left,char express,Integer right) {
        
        if(express == '+') {
            return left + right; 
        }
        else if(express == '-') {
            return left - right; 
        }
        else {
            return left * right; 
        }
        
    }//계산할 수 있는 메소드
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();//수식의 개수
        
        String str = sc.next();
        
        for(int i=0; i<str.length(); i++) {
            
            if(i % 2 == 0) {
                num.add(str.charAt(i)-'0');//숫자 list
            }
            else {
                op.add(str.charAt(i));//연산자 list
            }
            
        }
        
        dfs(0,str.charAt(0)-'0');
        
        System.out.println(max);
        
    }
    
    public static void dfs(int depth,int n) {
        
        if(depth >= op.size()) {
            
            if(n > max)
                max = n;
            
            return;
        }//끝에 도달했다면 max와 비교한 후, return
        
        dfs(depth+1 , cal(n, op.get(depth) , num.get(depth+1)));
        //1.괄호 x -> 단순 계산
        
        if(depth+2 < num.size()) {
            
            dfs(depth+2 , cal(n, op.get(depth) , cal(num.get(depth+1) , op.get(depth+1) , num.get(depth+2))));
            
            // 앞에 수식을 미리 계산하여 지금 숫자와 계산한다.
            // 앞에 수식을 미리 계산하기 때문에 괄호가 없는 depth+1와 다르게 depth+2로 다음 함수를 호출한다.
            
        }//if문을 사용하여 범위 내에 있는지 먼저 확인 
        //2. 괄호 o
        
    }
    
    
    
 
}