백준 - 연산자 끼워넣기(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/14888

[문제 설명]

연산자와 숫자를 줬을 때, 나올 수 있는 연산 결과 중 최댓값과 최솟값을 리턴하시오.

 

[접근 방법]

숫자는 어차피 차례대로 있을 것이고, 그 사이에 연산자를 일렬로 줄 세우는 문제다.

예 )

숫자 1 2 3

연산자 1 1 0 0

이렇게 있으면 1과 2사이에 연산자가 1개, 2와 3 사이에  연산자가 1개 들어 간다.

결국 2개의 연산자를 줄 세우면 되는 일, +와 -를 줄 세우면 전체 2개의 요소 중에서 2개를 줄세우는 것이라

2P2 => n*(n-1)*...*(n-r+1) => 2*1 => 2가 된다.

문제의 조건은 n개가 있으면 n개 모두 줄 세우는 것이라 => nPn => n*(n-1)*...*(n-n+1)=>n*(n-1)*...*(1)

즉, N!(팩토리얼)이 된다.

 

[Java 코드]

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

public class Main {
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    static int[] arrOfNumbers;
    static int[] arrOfOperators;
    private static boolean[] isExistNumber = new boolean[2000001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cntOfNumbers = Integer.parseInt(br.readLine());
        arrOfNumbers = new int[cntOfNumbers];
        int cntOfOperators = 0;
        arrOfOperators = new int[4];

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for (int i = 0; i < cntOfNumbers; i++) {
            arrOfNumbers[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < arrOfOperators.length; i++) {
            int cntOfOperator = Integer.parseInt(st.nextToken());
            arrOfOperators[i] = cntOfOperator;
            cntOfOperators += cntOfOperator;
        }

        recursion(0, arrOfNumbers[0], cntOfOperators);
        System.out.println(max);
        System.out.println(min);
    }

    private static void recursion(int idxOfNumber, int sum, int cntOfOperators) {
        if (cntOfOperators == 0) {
            max = Math.max(max, sum);
            min = Math.min(min, sum);
            return;
        }

        for (int i = 0; i < arrOfOperators.length; i++) {
            if (arrOfOperators[i] == 0) {
                continue;
            }
            arrOfOperators[i] -= 1;
            switch (i) {
                case 0 :
                    recursion(idxOfNumber+1, sum + arrOfNumbers[idxOfNumber+1], cntOfOperators-1);
                    break;
                // 연산자가 -
                case 1 :
                    recursion(idxOfNumber+1, sum - arrOfNumbers[idxOfNumber+1], cntOfOperators-1);
                    break;
                // 연산자가 *
                case 2 :
                    recursion(idxOfNumber+1, sum * arrOfNumbers[idxOfNumber+1], cntOfOperators-1);
                    break;
                case 3 :
                    recursion(idxOfNumber+1, sum / arrOfNumbers[idxOfNumber+1], cntOfOperators-1);
                    break;
            }
            arrOfOperators[i] += 1;
        }
    }
}

 

[Kotlin 코드] 

import java.io.BufferedReader
import java.io.InputStreamReader

lateinit var arrOfNumbers: IntArray
lateinit var arrOfOperators: IntArray
var max: Int = Int.MIN_VALUE
var min: Int = Int.MAX_VALUE
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cntOfNumbers = readLine().toInt()
    arrOfNumbers = readLine().split(" ").map { it.toInt() }.toIntArray()
    arrOfOperators = readLine().split(" ").map { it.toInt() }.toIntArray()

    recursion(0, arrOfNumbers[0])
    println(max)
    println(min)
}

fun recursion(idxOfNumber: Int, sum: Int) {
    if (idxOfNumber == arrOfNumbers.size-1) {
        max = max.coerceAtLeast(sum)
        min = min.coerceAtMost(sum)
        return
    }

    for (idxOfOperator in arrOfOperators.indices) {
        if (arrOfOperators[idxOfOperator] == 0) {
            continue
        }

        arrOfOperators[idxOfOperator] -= 1
        when (idxOfOperator) {
            0 -> recursion(idxOfNumber+1, sum+arrOfNumbers[idxOfNumber+1])
            1 -> recursion(idxOfNumber+1, sum-arrOfNumbers[idxOfNumber+1])
            2 -> recursion(idxOfNumber+1, sum*arrOfNumbers[idxOfNumber+1])
            3 -> recursion(idxOfNumber+1, sum/arrOfNumbers[idxOfNumber+1])
        }
        arrOfOperators[idxOfOperator] += 1
    }
}

https://github.com/ROUTINE-STUDY/Algorithm/pull/242