[백준 14888번] 연산자 끼워넣기 with Java

guswls·2024년 4월 26일

알고리즘

목록 보기

9/39

문제

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

코드

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

class Main {
	static int N;
	static int[] arr;
	static int[] oppr;
	static int min = Integer.MAX_VALUE;
	static int max = Integer.MIN_VALUE;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		oppr = new int[4];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			oppr[i] = Integer.parseInt(st.nextToken());
		}

		backTracking(1, arr[0]);

		System.out.println(max);
		System.out.println(min);

	}

	static void backTracking(int idx, int result) {
		if (idx == N) {
			max = Math.max(result, max);
			min = Math.min(result, min);
		}

		for (int i = 0; i < 4; i++) {
			if (oppr[i] == 0) {
				continue;
			}

			oppr[i]--;

			switch (i) {
			case 0:
				backTracking(idx + 1, result + arr[idx]);
				break;
			case 1:
				backTracking(idx + 1, result - arr[idx]);
				break;
			case 2:
				backTracking(idx + 1, result * arr[idx]);
				break;
			case 3:
				backTracking(idx + 1, result / arr[idx]);
				break;
			}
			
			oppr[i]++;
		}

	}
}

문제 이해

입력으로 숫자와 각 연산자+. -, *, -의 개수가 주어진다.
위 숫자와 수식으로 만들 수 있는 수 중 가장 작은 숫자와 가장 큰 숫자를 구하는 문제이다.

풀이 방법

백트래킹으로 접근하여야 한다.
oppr[4]에는 각 연산자의 개수, arr[N]에는 숫자들이 들어있다.
dfs를 수행할 때 넘겨주어야할 정보는 숫자의 현재 인덱스와 이전 수식의 결과 값이다.
연산자의 경우는 백트래킹을 통해 조합을 구해야 한다.
for문의 i값에 따라 연산을 결정하여 재귀호출을 한 후에 oppr[i]++;를 해줌으로써 다시 원상태로 돌려야 한다.
그래야 다음 연산에서 다시 그대로 활용할 수 있다.