[백준_14888번] 연산자 끼워넣기_삼성 SW 역량테스트

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

14888번: 연산자 끼워넣기

[문제]

 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

 

 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

 

 N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

 

[코드]

import java.util.Scanner;
/* 연산자 끼워넣기
 * 각 연산자의 개수를 입력받아 배열에 삽입한다
 * 이후 배열의 값이 0이 넘는다면 값을 줄이면서 재귀함수 호출 
 * 배열 값이 0이 된다면 다음 인덱스(연산자)로 넘어간다
 * 이 과정이 끝난다면 백트래킹을 위해 재귀호출을 종료하고 해당 연산자 개수를 늘려준다
 */
public class BaekJoon_14888 {
	public static int n;
	public static int[] operator=new int[4];
	public static int[] num;
	public static int max=Integer.MIN_VALUE;
	public static int min=Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		num=new int[n];
		
		for(int i=0;i<n;i++)
			num[i]=sc.nextInt();
		
		for(int i=0;i<4;i++)
			operator[i]=sc.nextInt();
		
		/* num의 첫 번쨰 원소가 매개변수로 주어졌기 때문에 
		 * depth은 1부터 시작하여 다음 숫자부터 계산하도록 한다.
		 */
		dfs(num[0],1);
		System.out.println(max);
		System.out.println(min);
	}
	
	public static void dfs(int number,int depth) {
		// 모든 숫자를 사용하여 계산이 끝난 경우 최소, 최댓값 계산
		if(depth==n) {
			max=Math.max(max, number);
			min=Math.min(min, number);
			return;
		}
		
		/*
		 * 해당 for문은 어떤 연산을 가장 먼저 수행할 것인지 결정해주는 역할을 한다.
		 * 그래야 모든 연산의 경우를 계산할 수 있다. 
		 */
		for(int i=0;i<4;i++) {
			// 연산자의 개수가 1개 이상인 경우
			if(operator[i]>0) {
				operator[i]-=1;
				
				switch(i) {
				case 0: dfs(number+num[depth],depth+1); break;
				case 1: dfs(number-num[depth],depth+1); break;
				case 2: dfs(number*num[depth],depth+1); break;
				case 3: dfs(number/num[depth],depth+1); break;
				}
				// 백트래킹을 위해 감소했던 연산자의 값 올려주기
				operator[i]+=1;
			}
		}
	}
}

 

[고찰]

 이번 문제는 그리 어렵지는 않았지만 한 가지의 실수로 인해 시간이 좀 걸렸던 문제였다. 연산자의 배열의 값이 1 이상일 경우에는 해당되는 연산자 배열의 값을 1 감소시키고 연산을 수행한 값과 depth를 1 증가시킨 값을 매개변수로 하여 재귀호출을 해주어야 하는데, 이때 백트래킹을 위해 감소했던 연산자 배열의 값을 복구해야 하는 과정을 이해하는 것이 어려웠다. 재귀함수의 호출이 끝나면 다음 연산을 위해 배열의 값을 복구해야 하며 아직은 재귀함수에 대한 공부가 더 필요할것 같다.