[백준 3주차 - 16637] 괄호 추가하기 (Java)

📌 문제

 

 

📝 풀이과정

1. +, -, * 와 같은 연산자 ArrayList와 숫자의 ArrayList로 나눈다 => 인덱스를 기반으로 연산을 하기 쉬워진다

for(int i=0;i<n;i++){
    if(i%2==0) nums.add(input.charAt(i)-'0'); //숫자 ArrayList
    else opers.add(input.charAt(i)); //연산자 ArrayList
}

 

2. 인덱스를 기반으로 해서 재귀함수로 탐색한다

 

예를 들어 3 + 8 * 7 라면 두가지 경우의 수가 나온다

1) (3 + 8) * 7 = 77  → nums[0]과 nums[1]을 opers[0]을 하고 난 후 나머지 계산

2) 3 + (8 * 7) = 59  → nums[1]과 nums[2]를 opers[1]을 하고 난 후 나머지 계산

 

 

 

 

 

 

💻 코드

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

public class Main{
	static ArrayList<Integer>nums=new ArrayList<>();
	static ArrayList<Character>opers=new ArrayList<>();
	static int n,ret=Integer.MIN_VALUE;
	static String input;
	
	static int operation(char a,int b,int c){
		if(a=='+') return b+c;
		if(a=='-') return b-c;
		if(a=='*') return b*c;
		return 0;
	}
	static void go(int here,int num){
    	//기저사례
		if(here==nums.size()-1){
			ret=Math.max(ret,num);
			return;
		}
		go(here+1, operation(opers.get(here),num,nums.get(here+1)));
		if(here+2<=nums.size()-1){
			int temp=operation(opers.get(here+1),nums.get(here+1),nums.get(here+2));
			go(here+2,operation(opers.get(here),num,temp));
		}
	}
    public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		n=Integer.parseInt(br.readLine());
		input=br.readLine();
		
		for(int i=0;i<n;i++){
			if(i%2==0) nums.add(input.charAt(i)-'0');
			else opers.add(input.charAt(i));
		}
		go(0,nums.get(0));
		System.out.println(ret);
	}
}