[실버1] 14888. 연산자 끼워넣기(Java)

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

14888번: 연산자 끼워넣기

추석 연휴에 푼거 끼워넣기,,

---

※  문제를 요약하면 아래와 같습니다.

▶ N개의 수로 이루어진 수열에서 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자 입력

▶ 연산자는 +, -, *, / 으로만 구성, 각각 1,2,3,4로 표현. 음수를 양수로 나눌 때는 양수로 바꾼뒤 몫을 취하고 음수로 변경

▶ N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 출력

▶ Input : 첫 번째 줄에 수의 갯수 N, 둘째줄에는 수열, 마지막 줄에는 차례대로 +,-,*,/ 연산자의 갯수 입력

▶ Output : 첫째 줄에 최댓값, 두번째 줄에 최소값 출력

---

◈ Input - 1

2
5 6
0 0 1 0

◈ Output - 1

30
30

◈ Input - 2

3
3 4 5
1 0 1 0

◈ Output - 2

35
17

◈ Input - 3

6
1 2 3 4 5 6
2 1 1 1

◈ Output - 3

54
-24

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 1, 2, 3, 4가 각각 +,-,*,/의 연산을 할 수 있는 함수 구현

▶ N과 M문제 풀이와 비슷하게 구현

    1. M만큼 숫자를 배열에 저장하여 재귀함수를 구현했던 것 처럼 처럼 N-1개만큼 연산자를 저장한다.

    2. N-1개 만큼 저장했을 때 각 배열에 해당하는 연산을 수에 맞게 차례대로 진행

    3. 모든 경우를 탐색하여 최댓값, 최소값 출력

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, nMax, nMin, nCalculate;
	static int[] narr;
	static int[] ncalArr;
	static int[] narrSearch;
	static boolean[] barrVisit;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(bReader.readLine());

		narr = new int[N];
		barrVisit = new boolean[N - 1];
		ncalArr = new int[N - 1];
		narrSearch = new int[N - 1];

		// 수열 입력 받구
		StringTokenizer st = new StringTokenizer(bReader.readLine());
		for (int i = 0; i < N; i++) {
			narr[i] = Integer.parseInt(st.nextToken());
		}

		// 각각의 연산자 갯수 입력 받자
		// + - * /
		// 1,2,3,4 로 연산자를 넘버링
		int nCalIndex = 0;
		
		st = new StringTokenizer(bReader.readLine());
		for (int i = 1; i <= 4; i++) {
			int nCal = Integer.parseInt(st.nextToken());
			for (int j = 0; j < nCal; j++) {
				ncalArr[nCalIndex++] = i;
			}
		}

		nMax = Integer.MIN_VALUE;
		nMin = Integer.MAX_VALUE;
		Operator(0);
		
		bWriter.write(nMax + "\n" + nMin);
		bWriter.close();

	}

	private static void Operator(int nIndex) {
		// TODO Auto-generated method stub
		// 기저 조건
		// 연산 끝났따
		// 연산자는 N-1개 만큼 사용 가능
		if (nIndex == N - 1) {
			
			// 최초 계산 해주고
			int nCal = narr[0];
			// 지금까지 모여온 연산을 바탕으로 계산 고고
			for(int i = 0; i < N-1; i++) {
				nCal = getCal(nCal, narr[i+1], narrSearch[i]);
			}
			
			if (nMax < nCal)
				nMax = nCal;

			if (nMin > nCal)
				nMin = nCal;

			return;
		}

		// 재귀 조건
		// 연산자의 횟수가 중요하다
		for (int i = 0; i < N - 1; i++) {
			if (!barrVisit[i]) {
				narrSearch[nIndex] = ncalArr[i];
				barrVisit[i] = true;
				Operator(nIndex+1);
				barrVisit[i] = false;
			}
		}
	}
	
	private static int getCal(int nFstNum, int nSecNum, int nCalNum) {
		if(nCalNum == 1) // +
			return nFstNum+nSecNum;
		if(nCalNum == 2) // -
			return nFstNum-nSecNum;
		if(nCalNum == 3) // *
			return nFstNum*nSecNum;
		if(nCalNum == 4) {
			// 나누기
			// 분모가 음수일 때
			if(nSecNum == 0)
				return 0;
			if(nFstNum < 0 && nSecNum >= 0) {
				int nResult = (nFstNum * -1) / nSecNum;
				return nResult * -1;
			}
			
			return nFstNum / nSecNum;
		}
		
		return 0;
	}

}

---

Good 추석 연휴! (피드백 감사합니다!)