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

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

연산자와 숫자가 주어질 때, 연산 방법에 따라 최대 / 최소 값을 구하는 문제

 

2. 풀이

 

이 문제는 어려울 것 없이 완전 탐색으로 해결할 수 있다. 방법은 2가지이다.

① 숫자의 위치가 정해진 상태에서 연산자 위치 조정
② 연산자 위치가 정채진 상태에서 숫자 위치 조정

 

이 문제에선 연산자의 우선 순위에 따른 계산은 고려하지 않아도 되기 때문에 위치만 정해진다면 그 결과값을 모두 고려하여 최대 / 최소값을 구하면 된다.

자세한 내용은 코드를 통해 이해해보자. 아래에서 재귀 / 순열을 사용하여 문제를 해결하였다.

재귀로 푼 경우는 ①의 방식으로, 순열은 ②의 방식으로 해결하였다.

 

 

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;
    }
}

 

 

② 순열로 해결하기

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

public class Main{
    static int n;
    static int[] num;
    static int[] op;
    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];
        op = new int[n-1];
        for(int i=0; i < n; i++){
            num[i] = Integer.parseInt(st.nextToken());
        }

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


        // ***************** 완전 탐색으로 결과값 도출 ********************
        while(true){
            calc();
            boolean isNext = perm();
            if(!isNext) break;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(max).append("\n").append(min);
        System.out.println(sb);
        // ***************** 완전 탐색으로 결과값 도출 완료 ********************

        br.close();
    }

    // 다음 순열을 구하는 메소드
    private static boolean perm(){
        int m = n-1;
        int i = m-1;
        while(i > 0 && op[i-1] >= op[i]) i--;
        if(i <= 0) return false;

        int j=i-1;
        while(j < m-1 && op[j+1] > op[i-1]) j++;
        swap(i-1, j);

        j = m-1;
        while(i < j){
            swap(i, j);
            i+=1; j-=1;
        }
        return true;
    }

    private static void swap(int i, int j){
        int temp = op[i];
        op[i] = op[j];
        op[j] = temp;
    }

    // 전달된 연산자 값과 함께 값을 연산하여 반환함
    private static int calc(){
        int result = num[0];

        for(int i=1; i < n; i++){
            if(op[i-1] == 0){
                result += num[i];
            } else if(op[i-1] == 1){
                result -= num[i];
            } else if(op[i-1] == 2){
                result *= num[i];
            } else {
                if(result < 0){
                    result = (result * -1) / num[i] * -1;
                } else {
                    result /= num[i];
                }
            }
        }
        max = Math.max(max, result);
        min = Math.min(min, result);
        return result;
    }
}

 

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