[백준] 15658. 연산자 끼워넣기 (2)

문제 링크

[백준] 15658. 연산자 끼워넣기 (2)

풀이 과정

완전탐색 문제입니다.

for (int i = 0; i < N; i++) arr[i] = sc.nextInt();
for (int i = 0; i < 4; i++) opCnt[i] = sc.nextInt();

dfs(1, arr[0], opCnt);

먼저, 피연산자들을 입력 받아 배열 arr에 저장하고, 사칙 연산자의 개수를 입력 받아 배열 opCnt에 저장합니다. 이후 dfs()를 호출합니다. 이 때, 인덱스를 1로, 누적합을 arr[0]으로 설정함으로써, 두 번째 피연산자부터 연산자를 적용시켜 계산을 하게 됩니다.

static void dfs(int idx, int sum, int[] opCnt) {
    if (idx == N) {
        min = Math.min(min, sum);
        max = Math.max(max, sum);
        
        return;
    }

    if (opCnt[0] > 0) {
        opCnt[0]--;
        dfs(idx + 1, sum + arr[idx], opCnt);
        opCnt[0]++;
    }
    if (opCnt[1] > 0) {
        opCnt[1]--;
        dfs(idx + 1, sum - arr[idx], opCnt);
        opCnt[1]++;
    }
    if (opCnt[2] > 0) {
        opCnt[2]--;
        dfs(idx + 1, sum * arr[idx], opCnt);
        opCnt[2]++;
    }
    if (opCnt[3] > 0) {
        opCnt[3]--;
        dfs(idx + 1, sum / arr[idx], opCnt);
        opCnt[3]++;
    }
}

dfs()는 현재까지의 계산 결과 sum에 현재 피연산자 arr[idx]를 계산한 결과를 파라미터로 재귀함수를 호출합니다.

코드

import java.util.Scanner;

public class Main {
    static int N;
    static int[] arr;
    static int[] opCnt = new int[4];
    static int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N];
        
        for (int i = 0; i < N; i++) arr[i] = sc.nextInt();
        for (int i = 0; i < 4; i++) opCnt[i] = sc.nextInt();

        dfs(1, arr[0], opCnt);

        System.out.println(max + "\n" + min);
    }

    static void dfs(int idx, int sum, int[] opCnt) {
        if (idx == N) {
            min = Math.min(min, sum);
            max = Math.max(max, sum);
            
            return;
        }

        if (opCnt[0] > 0) {
            opCnt[0]--;
            dfs(idx + 1, sum + arr[idx], opCnt);
            opCnt[0]++;
        }
        if (opCnt[1] > 0) {
            opCnt[1]--;
            dfs(idx + 1, sum - arr[idx], opCnt);
            opCnt[1]++;
        }
        if (opCnt[2] > 0) {
            opCnt[2]--;
            dfs(idx + 1, sum * arr[idx], opCnt);
            opCnt[2]++;
        }
        if (opCnt[3] > 0) {
            opCnt[3]--;
            dfs(idx + 1, sum / arr[idx], opCnt);
            opCnt[3]++;
        }
    }
}