[알고리즘] 백준 14888 연산자 끼워넣기 -백트랙킹- 자바 코틀린

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

 

 

 

백준 백트랙킹 단계별풀기의 14888번 연산자 끼워넣기를 풀어봤습니다.

 

숫자 리스트와(n) 숫자를 연산할 만큼의(n-1) 사칙연산자의 개수가 주어집니다.  가장 큰 경우와 작은 경우를 구하는 문제입니다.

 

1. 먼저 탐색은 입력 숫자만큼일 때 까지 재귀를 돌립니다.

2. 연산자는 총 4개입니다. 4크기의 연산자 배열을 만듭니다.

3. 모든 연산자의 경우를 탐색합니다. 그리고 각 연산자에 맞는 값을 재귀로 넘겨줍니다. 탐색을 하기 전 해당 연산자 개수를 -1 해주고 탐색을 완료하면 +1을 해주도록 합니다.

3. 마지막 숫자의 연산까지 마친 경우 최솟값과 최댓값을 비교해서 저장해줍니다.

 

 

 

 

다음은 풀이입니다.

 

[Java]

import java.util.Scanner;

public class Main {
    private static int[] opArr = new int[4];
    private static int[] numArr;
    private static int max = Integer.MIN_VALUE;
    private static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        numArr = new int[size];
        for (int i = 0; i < numArr.length; i++) {
            numArr[i] = sc.nextInt();
        }
        for (int i = 0; i < opArr.length; i++) {
            opArr[i] = sc.nextInt();
        }
        dfs(numArr[0], 1);
        System.out.println(max);
        System.out.println(min);
    }

    private static void dfs(int num, int index) {
        if (index == numArr.length) { 
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }
        for (int i = 0; i < opArr.length; i++) { // 연산자 경우의 수 탐색
            if (opArr[i] > 0) {
                opArr[i]--;
                if (i == 0) {
                    dfs(num + numArr[index], index + 1);
                } else if (i == 1) {
                    dfs(num - numArr[index], index + 1);
                } else if (i == 2) {
                    dfs(num * numArr[index], index + 1);
                } else {
                    dfs(num / numArr[index], index + 1);
                }
                opArr[i]++;
            }
        }

    }
}

 

 

[Kotlin]

import java.util.*

private val opArr = IntArray(4)
lateinit var numArr: IntArray
private var max = Integer.MIN_VALUE
private var min = Integer.MAX_VALUE


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val size = sc.nextInt()
    numArr = IntArray(size)
    for (i in numArr.indices) {
        numArr[i] = sc.nextInt()
    }
    for (i in opArr.indices) {
        opArr[i] = sc.nextInt()
    }
    dfs(numArr[0], 1)
    println(max)
    println(min)
}

private fun dfs(num: Int, index: Int) {
    if (index == numArr.size) {
        max = Math.max(max, num)
        min = Math.min(min, num)
        return
    }
    for (i in opArr.indices) {
        if (opArr[i] > 0) {
            opArr[i]--
            if (i == 0) {
                dfs(num + numArr[index], index + 1)
            } else if (i == 1) {
                dfs(num - numArr[index], index + 1)
            } else if (i == 2) {
                dfs(num * numArr[index], index + 1)
            } else {
                dfs(num / numArr[index], index + 1)
            }
            opArr[i]++
        }
    }

}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다 !!