백준(BOJ) 15658 : 연산자 끼워넣기 (2) (실버2) / 자바(Java) 풀이

문제

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

3줄 요약

1. 수의 개수 N, 수열 A, 그리고 사용 가능한 연산자의 개수를 입력받습니다.
2. 백트래킹을 활용하여 재귀 함수를 통해 연산자를 배치하는 모든 경우를 탐색하고, 각 경우에 대해 연산 결과를 계산합니다.
   • 재귀 함수에서는 현재 배치한 연산자의 개수를 저장하는 배열 visited를 사용하여 연산자를 배치하고, 배치된 연산자에 따라 연산을 수행합니다.
   • 연산자 배치가 완료되었을 때, 연산 결과를 최댓값과 최솟값과 비교하여 갱신합니다.
   • 백트래킹을 적용하여 현재 배치한 연산자로 인해 더 이상 탐색할 필요가 없는 경우, 해당 연산자를 배치하지 않고 다른 연산자를 배치하도록 합니다.
3. 모든 경우를 탐색한 후, 최댓값과 최솟값을 출력합니다. 이 문제에서는 백트래킹을 활용한 재귀 함수를 통해 연산자 배치의 모든 경우를 효율적으로 탐색하고, 각 경우에 대해 연산을 수행하여 최댓값과 최솟값을 구할 수 있습니다.

코드

package boj15658;

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // 입력 파일에서 데이터 읽기 (테스트용)
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 수의 개수 N 입력받기
        int N = Integer.parseInt(br.readLine());
        
        // 수열 A 입력받기
        String[] arr;
        arr = br.readLine().split(" ");
        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(arr[i]);
        }
        
        // 연산자의 개수 입력받기
        // visited 배열에 각 연산자(+, -, *, /)의 개수를 저장
        // visited[0]: '+' 연산자의 개수
        // visited[1]: '-' 연산자의 개수
        // visited[2]: '*' 연산자의 개수
        // visited[3]: '/' 연산자의 개수
        arr = br.readLine().split(" ");
        for (int i = 0; i < 4; i++) {
            visited[i] = Integer.parseInt(arr[i]);
        }
        
        br.close();
        
        // 백트래킹을 활용한 연산자 배치 및 최댓값, 최솟값 계산
        // 초기 depth는 1, 초기 값은 수열의 첫 번째 수 A[0]으로 설정
        recursion(N, 1, A[0]);
        
        // 결과 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(max)); // 최댓값 출력
        bw.write("\n");
        bw.write(Integer.toString(min)); // 최솟값 출력
        bw.flush();
        bw.close();
    }
    
    public static int[] A; // 수열 A
    public static int[] visited = new int[4]; // 연산자의 개수를 저장할 배열
    public static int max = Integer.MIN_VALUE; // 최댓값을 저장할 변수
    public static int min = Integer.MAX_VALUE; // 최솟값을 저장할 변수
    
    public static void recursion(int N, int depth, int val) {
        // 연산자 배치가 완료되었을 때 (모든 수를 사용한 경우)
        if (N == depth) {
            max = Math.max(max, val); // 현재 값과 최댓값 비교하여 갱신
            min = Math.min(min, val); // 현재 값과 최솟값 비교하여 갱신
            return;
        }
        
        // 연산자 배치
        for (int i = 0; i < 4; i++) {
            if (visited[i] == 0) {
                // 해당 연산자를 모두 사용한 경우 건너뛰기
                continue;
            }
            
            visited[i]--; // 해당 연산자 사용 표시
            
            switch (i) {
                case 0: {
                    // '+' 연산자인 경우
                    recursion(N, depth + 1, val + A[depth]);
                    break;
                }
                case 1: {
                    // '-' 연산자인 경우
                    recursion(N, depth + 1, val - A[depth]);
                    break;
                }
                case 2: {
                    // '*' 연산자인 경우
                    recursion(N, depth + 1, val * A[depth]);
                    break;
                }
                case 3: {
                    // '/' 연산자인 경우
                    recursion(N, depth + 1, val / A[depth]);
                    break;
                }
            }
            
            visited[i]++; // 해당 연산자 사용 해제 (백트래킹)
        }
    }
}