[BOJ] 14888 연산자 끼워넣기 - Java

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

14888번: 연산자 끼워넣기

---

1. 문제

N개의 숫자들, 연산자 개수가 각각 주어질 때 만들 수 있는 결과값의 최댓값과 최솟값을 출력한다.

2. 풀이

백트래킹 문제이다.

결과값을 파라미터로 넘기면서 다음 숫자와 연산해주었다.

연산자 4개를 매번 하나하나 개수 체크를 하면서 개수가 있는 것부터 +,-,*,/ 순서로 연산을 해주었다.

다음 연산으로 넘어가는 dfs를 실행하기 전 oper[operIdx]--; 로 연산자를 사용했고 dfs가 끝난 후 oper[operIdx]++;로 연산자 사용 개수를 다시 늘려주었다.

연산은 calculator 함수를 따로 빼서 거기서 연산을 해주었고 마지막 숫자까지 오게되면 max, min을 갱신해주었다.

 

3. 코드

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

public class Main {
    
	static int N, max, min, nums[], opers[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		nums = new int[N];
		opers = new int[4];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<4; i++) {
			opers[i] = Integer.parseInt(st.nextToken());
		}
		// 입력 끝
		
		max = Integer.MIN_VALUE;
		min = Integer.MAX_VALUE;
		dfs(1, nums[0]);
		System.out.println(max);
		System.out.println(min);
	}
	
	static void dfs(int numIdx, int sum) {
		if (numIdx == N) {
			max = Math.max(max, sum);
			min = Math.min(min, sum);
			return;
		}
		
		for (int operIdx=0; operIdx<4; operIdx++) {
			if (opers[operIdx] > 0) {
				int res = calculator(sum, nums[numIdx], operIdx);
				
				opers[operIdx] -= 1;
				dfs(numIdx+1,  res);
				opers[operIdx] += 1;
			}
		}
	}
	
	static int calculator(int sum, int num, int oper) {
		int res = 0;
		switch(oper) {
		case 0: //+
			res = sum + num;
			break;
		case 1: //-
			res = sum - num;
			break;
		case 2: //*
			res = sum * num;
			break;
		case 3: // /
			res = sum / num;
			break;
		}
		return res;
	}
}

4. 사담

아침에 푸는 백트래킹.. 풀어서 너무 뿌듯하다.

알고리즘 고수가 되고싶다