알고리즘 풀이 - 백준 15658(연산자 끼워넣기 (2), 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N개의 수와 N-1개 이상, 4N개 미만의 연산자가 주어졌을 때, 연산을 수행하는 경우에 따라 최소/최대값을 구하는 문제

 

 

2. 풀이

 

숫자 N개가 주어질 때, 4N이하의 연산자가 주어진다면 연산자를 어떻게 배치했을 때 결과가 최대 / 최소값이 되는 지를 구하는 문제이므로 완전 탐색을 통해 해결할 수 있다.

단순히 재귀를 통해 전체 숫자가 N개이므로 N-1개의 연산자를 각 위치에 모두 대입하여 그 결과를 구한 뒤 출력하면 해결할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static int[] num;
    static int[] op = new int[4]; // 0(+), 1(-), 2(*), 3(/)
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // ***************** 주어진 숫자, 연산자 저장 ********************
        n = Integer.parseInt(br.readLine());

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

        st = new StringTokenizer(br.readLine());
        for(int i=0; i < 4; i++){
            op[i] = Integer.parseInt(st.nextToken());
        }
        // ***************** 주어진 숫자, 연산자 저장 완료 ********************


        // ***************** 완전 탐색으로 결과값 도출 ********************
        bruteForce(1, num[0]);
        StringBuilder sb = new StringBuilder();
        sb.append(max).append("\n").append(min);
        System.out.println(sb);
        // ***************** 완전 탐색으로 결과값 도출 완료 ********************

        br.close();
    }

    // 완전 탐색을 수행하는 메소드
    private static void bruteForce(int idx, int cur){
        if(idx == n) {
            max = Math.max(max, cur);
            min = Math.min(min, cur);
            return;
        }

        // 각각의 연산자를 대입하여 완전 탐색 수행
        for(int i=0; i < 4; i++){
            if(op[i] == 0) continue;
            op[i]--;
            
            // 현재값, 연산자 index, 다음 숫자를 전달하여 연산값 전달받는다.
            int temp = calc(cur, i, num[idx]);
            
            // 전달받은 숫자로 완전 탐색 지속 수행
            bruteForce(idx+1, temp);
            op[i]++;
        }
    }

    // 전달된 연산자 값과 함께 값을 연산하여 반환함
    private static int calc(int y, int i, int x){
        int result = 0;
        if(i == 0){
            result = y + x;
        } else if(i == 1) {
            result = y - x;
        } else if(i == 2) {
            result = y * x;
        } else {
            if(y < 0){
                result = (y*-1) / x * -1;
            } else {
                result = y / x;
            }
        }
        return result;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.