[JAVA] BOJ(백준) - 연산 최대로 - 21943

문제내용

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

21943번: 연산 최대로

 N$N$개의 양의 정수 Xi$X_{i}$와 곱하기 연산자, 더하기 연산자가 총 N−1$N - 1$개가 존재하고 괄호는 무수히 많이 사용해도 된다. 이 연산에는 곱하기 연산자와 더하기 연산자의 우선순위가 동일하다.

정수와 연산자는 아래와 같이 배치해야한다. 정수의 순서는 바꿔도 상관없다.

예를 들어 정수 1$1$, 2$2$, 3$3$이 있고 더하기 연산자와 곱하기 연산자가 각각 하나 있다고 가정하면 아래와 같이 만들 수 있다. 

예를 들어, 수 1,2,4,5,7,8$1, 2, 4, 5, 7, 8$와 더하기 연산자가 4개 곱하기 연산자가 1개 있다고 하자. 괄호를 이용하여 최대값을 구하는 방법 중 일부이다.

•  (((1+2)+4)+7)×(5+8)$(((1+2)+4)+7) × (5+8)$ 
•  ((1+2)+(4+7))×(5+8)$((1+2)+(4+7)) × (5+8)$ 
•  (1+(2+4)+7)×(5+8)$(1+(2+4)+7) × (5+8)$ 
•  (1+2+4+7)×(5+8)$(1+2+4+7) × (5+8)$ 

연산을 잘 이용하여 값을 최대로 만들어 보자.

입력

첫째 줄에 입력될 양의 정수 개수를 뜻하는 N$N$이 주어진다.

그 다음줄에는 N$N$개의 양의 정수 Xi$X_{i}$가 공백으로 구분되어 주어진다.

마지막 줄에는 더하기 연산자의 개수 P$P$와 곱하기 연산자의 개수 Q$Q$가 공백으로 구분되어 주어진다.

---

문제풀이

주어진 수를 조작 && 연산자 조작으로 푸는 문제이다.

푸는방법은 여러가지 겠지만 필자는 백트래킹 2번으로 풀었다. 조금 복잡해 보일수 있으나 크게 생각한다면 별다르지 않을거라고 생각한다. 그리고 처음에 백트래킹을 2번쓰면 시간초과가 나지 않을까 생각했다. 그리고 대충 계산해보니 수의 조합 최대는 8!=40320이고, 연산자의 개수는 +,* 2개 뿐이고 이전에 표시했던 자리의 중복을 제거해서 경우의 수를 더 줄인다면 가능할꺼라고 생각했다.

 

1. 수 조합하기
   문제에서 주어진 수들은 순서대로 그대로 있는게 아니라 위치가 서로 바뀔수 있다는 점을 알아야한다.
   따라서 백트래킹을 이용해 모든 수의 조합을 만든다.
   
   
2. 연산자 조합하기
   연산자도 수와 마찬가지다. +, * 가 어느 위치에 있는지 정해져 있는게 아니기 때문에 수를 조합하고 나서는 연산자를 백트래킹을 이용해 조합해준다.
   
   
3. 조합된거 계산
   조합된 수 + 조합된 연산자 를 이용해서 값을 계산해준다. 나는 계산할때 연산자 표시를 boolean 배열로 했고 true 일경우 +, false 일경우 * 로 표현했다.
   
   그리고 +를 먼저 전부 계산하고, 계산된 모든 값들을 곱해줘서 최댓값을 찾았다. 이때 +로 계산된 값들을 넣어줄 공간이 필요한데 이는 int[] sum = new int[곱하기갯수+1] 로 했줬다.
   예를들어, (1+2+3)*(7+5)*8 이라고 한다면.
   결국 * 기준으로 3개의 공간이 필요하다는걸 알수 있다.

자세한 내용을 코드로 ㄱㄱ

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main { 
	static boolean[] check;
	static int plus, mul, max;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		check = new boolean[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		plus = Integer.parseInt(st.nextToken());
		mul = Integer.parseInt(st.nextToken());
		max = Integer.MIN_VALUE;
		
		
		boolean[] oper = new boolean[n-1];//연산자 표현, true==+ , false==*
		StringBuilder sb = new StringBuilder();//조합된 수 표현
		back(0,arr,oper,sb);//백트래킹 ㄱㄱ
		System.out.println(max);
	}
	
	//수의 조합 만들기
	public static void back(int depth, int[] arr, boolean[] oper, StringBuilder sb) {
		if(depth==arr.length) {
			int[] nums = new int[arr.length];
			for(int i=0; i<sb.length(); i++) 
				nums[i] = sb.charAt(i)-'0';
			
			back2(0,0,nums,oper);//연산자 조합
		}
		
		for(int i=0; i<check.length; i++) {
			if(check[i]) continue;
			check[i]=true;
			sb.append(arr[i]);
			back(depth+1, arr, oper, sb);
			check[i]=false;
			sb.delete(sb.length()-1, sb.length());
		}
	}
	
	//연산자 조합 / a:이전에 +했던 자리는 건너뛰기 / depth: +개수 / nums:조합된수들 / oper: 연산자 표현 
	public static void back2(int a, int depth, int[] nums, boolean[] oper) {
		//true를 + 개수만큼 해줬을때 종료.
		if(depth==plus) {
			int[] sum = new int[mul+1];// +한 값을 넣어 주기위한 공간 
			int idx=0;
			for(int i=0; i<oper.length; i++) {
				//첫번째 연산자가 +일때는 sum에 더한값 넣어줌
				if(i==0 && oper[i]) {
					sum[idx] += nums[i]+nums[i+1];
				}
				//현재 +일때 이전에도 +라면 이전까지 더한 sum값에 현재 더할 nums를 더해줌.
				else if(oper[i] && oper[i-1]) {
					sum[idx] += nums[i+1];
				}
				//현재 *일때는 이전값에서 더하는게 아님.
				//새로운 sum을 만들어줌.
				else if(!oper[i]) {
					idx++;
					sum[idx] += nums[i+1];
				}
				//현재 +인데 이전에 *였을때도 sum에 현재 더할 nums를 더해줌. 
				else if(oper[i] && !oper[i-1]) {
					sum[idx] += nums[i+1];
				}
			}
			//첫번째값이 *였다면 sum[0]에 nums[0] 넣어주기
			if(!oper[0]) sum[0] = nums[0];
			int res = 1;
			for(int s:sum) res *= s;//곱하기
			max = Math.max(res, max);
		}
		
		//+ 개수만큼 표시해주기
		for(int i=a; i<oper.length; i++) {
			if(oper[i]) continue;
			oper[i]=true;
			back2(i,depth+1, nums, oper);
			oper[i]=false;
		}
	}
}

---

마치며

Java를 사용해 푼 블로그 중에 참고할만한 블로그가 딱히 없어서 푸는데 삼성 문제만큼 시간이 좀 걸렸던 문제다.. 아무튼 풀면서 나도 도움이 됐지만 누군가에게 도움이 됐으면 좋겠다.