[백준] 14888 연산자 끼워넣기 - 자바

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

14888번: 연산자 끼워넣기

 

문제 풀이

 

입력 조건과 시간제한을 보면 꽤나 여유롭게 풀 수 있는 문제로 완전탐색을 진행하여 풀 것이다. dfs, bfs 뭐든 상관 없지만 웬만하면 재귀를 이용한 dfs가 더욱 간단한 것 같다.

완전탐색 구현 및 종료조건만 잘 정한다면 비교적 쉽게 구현 가능하다.

다음 코드가 왜 완전탐색인지 이해가 안 간다면 작은 값의 N으로 샘플을 직접 손으로 따라가거나 디버깅을 통해 확인해보면 쉽게 이해할 수 있을 것이다.

 

여기서 종료 조건은 연산자의 개수 즉 N-1번으로 본인은 dfs(1)부터 시작하여 N이 됐을 때까지 진행하였다.

참고!
6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 가진다고 하는데 여기서 60이 나온 이유는 숫자는 그대로 둔다 했고 중간에 총 5개의 연산을 껴넣으며 순서가 존재하고 중복이 있다. 즉, 증복순열로 5!/2! = 60이 나온 것이다.
알고리즘을 설계하고 문제를 푸는 데에는 지장 없으니 참고만 하고 넘어가자.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static int n;
    public static int[] nums;
    public static int plus, minus, mul, div;
    public static int min = Integer.MAX_VALUE;
    public static int max = Integer.MIN_VALUE;

    // dfs를 통한 완전탐색
    public static void dfs(int i, int result) {
        // 모든 연산자를 다 사용한 경우, 최솟값과 최댓값 업데이트
        if (i == n) {
            min = Math.min(min, result);
            max = Math.max(max, result);
        }
        else {
            // 각 연산자에 대하여 재귀적으로 수행
            if (plus > 0) {
                plus -= 1;
                dfs(i + 1, result + nums[i]);
                plus += 1;
            }
            if (minus > 0) {
                minus -= 1;
                dfs(i + 1, result - nums[i]);
                minus += 1;
            }
            if (mul > 0) {
                mul -= 1;
                dfs(i + 1, result * nums[i]);
                mul += 1;
            }
            if (div > 0) {
                div -= 1;
                dfs(i + 1, result / nums[i]);
                div += 1;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        nums = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        StringTokenizer st = new StringTokenizer(br.readLine());

        plus = Integer.parseInt(st.nextToken());
        minus = Integer.parseInt(st.nextToken());
        mul = Integer.parseInt(st.nextToken());
        div = Integer.parseInt(st.nextToken());

        // 첫 번째 숫자를 시작으로 dfs 완전탐색 실행
        dfs(1, nums[0]);

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