[알고리즘] 백준 15658 연산자 끼워넣기 (2) -백트래킹- 자바, 코틀린

 

 

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

15658번: 연산자 끼워넣기 (2)

 

 

 

백준 유형별풀기에 백트래킹 문제  연산자 끼워넣기 (2) 를 풀어봤습니다. 

연산자 우선순위는 배제하고 정해지 연산자별 개수로 가장 큰 수식과 작은 수식 결과를 도출해내는 문제였습니다.

 

연산자 개수를 한개씩 줄여가며 백트래킹을 돌리면 되는 문제였습니다.

그리고 이렇게 두 개의 값을 연산하는 문제인 경우 첫번째 값을 넣어주고 돌리면 풀기 좋습니다 :)

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

public class Main {
    private static int N;
    private static int[] op = new int[4];
    private static int[] arr;
    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);
        N = sc.nextInt();
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 0; i < 4; i++) {
            op[i] = sc.nextInt();
        }
        dfs(1, op, arr[0]);
        System.out.println(max);
        System.out.println(min);
    }

    private static void dfs(int depth, int[] op, int result) {
        if (depth == N) {
            max = Math.max(max, result);
            min = Math.min(min, result);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (op[i] == 0) {
                continue;
            }
            op[i]--;
            switch (i) {
                case 0:
                    dfs(depth + 1, op, result + arr[depth]);
                    break;
                case 1:
                    dfs(depth + 1, op, result - arr[depth]);
                    break;
                case 2:
                    dfs(depth + 1, op, result * arr[depth]);
                    break;
                case 3:
                    dfs(depth + 1, op, result / arr[depth]);
                    break;
            }
            op[i]++;
        }
    }
}

 

[Kotlin]

import java.util.*


private var N = 0
private val op = IntArray(4)
private lateinit var arr: IntArray
private var max = Int.MIN_VALUE
private var min = Int.MAX_VALUE
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    arr = IntArray(N)
    for (i in 0 until N) {
        arr[i] = sc.nextInt()
    }
    for (i in 0..3) {
        op[i] = sc.nextInt()
    }
    dfs(1, op, arr[0])
    println(max)
    println(min)
}

private fun dfs(depth: Int, op: IntArray, result: Int) {
    if (depth == N) {
        max = Math.max(max, result)
        min = Math.min(min, result)
        return
    }
    for (i in 0..3) {
        if (op[i] == 0) {
            continue
        }
        op[i]--
        when (i) {
            0 -> dfs(depth + 1, op, result + arr[depth])
            1 -> dfs(depth + 1, op, result - arr[depth])
            2 -> dfs(depth + 1, op, result * arr[depth])
            3 -> dfs(depth + 1, op, result / arr[depth])
        }
        op[i]++
    }
}

 

 

https://github.com/mtjin/algorithm_practice/commit/d982e5e058e2b74ea434ce44efb8fd68bf92ea4f

백준 15658 풀이 · mtjin/algorithm_practice@d982e5e

 

 

오랜만에 자바와 코틀린으로 알고리즘을 풀어봤네요.

뇌가 굳지 않게 꾸준히 해야겠습니다...

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