백준 14888: 연산자 끼워넣기

문제 보러 가기 👈

💡 풀이

• dfs사용하여 모든 경우를 탐색

구현 코드(Python) 👇

import sys

input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

max_result = float('-inf')
min_result = float('inf')

def dfs(depth, total, plus, minus, mul, div):
    global max_result, min_result

    if depth == N:
        max_result = max(max_result, total)
        min_result = min(min_result, total)
        return
    
    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, mul, div)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, mul, div)
    if mul:
        dfs(depth + 1, total * num[depth], plus, minus, mul - 1, div)
    if div:
        dfs(depth + 1, int(total / num[depth]), plus, minus, mul, div - 1)

dfs(1, num[0], op[0], op[1], op[2], op[3])
print(max_result)
print(min_result)

구현 코드(Java) 👇

import java.util.Scanner;
import java.lang.Math;

public class Main {
	static int N;
	static int[] nums;
	static Integer max_value = Integer.MIN_VALUE, min_value = Integer.MAX_VALUE;
	
	public static void dfs(int depth, int result, int plus, int minus, int mul, int div) {
		if(depth == N) {
			max_value = Math.max(max_value, result);
			min_value = Math.min(min_value, result);
			return;
		}
		
		if(plus != 0) {
			dfs(depth + 1, result + nums[depth], plus - 1, minus, mul, div);
		}
		if(minus != 0) {
			dfs(depth + 1, result - nums[depth], plus, minus - 1, mul, div);
		}
		if(mul != 0) {
			dfs(depth + 1, result * nums[depth], plus, minus, mul - 1, div);
		}
		if(div != 0) {
			dfs(depth + 1, result / nums[depth], plus, minus, mul, div - 1);
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] ops = new int[4];
		
		N = sc.nextInt();
		nums = new int[N];
		for(int i = 0; i < N; i ++) {
			nums[i] = sc.nextInt();
		}
		
		for(int i = 0; i < 4 ; i ++) {
			ops[i] = sc.nextInt();
		}
		
		dfs(1, nums[0], ops[0], ops[1], ops[2], ops[3]);
		System.out.println(max_value);
		System.out.println(min_value);
		
	}

}

---

📒 dfs로 전달하는 매개변수의 개수를 줄이는 코드

구현 코드(Python) 👇

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
ops = list(map(int, sys.stdin.readline().split()))  #+, - , x, %

max_value = float('-inf')
min_value = float('inf')

def dfs(depth, result):
    global max_value, min_value

    if depth == N:
        max_value = max(max_value, result)
        min_value = min(min_value, result)
        return
    
    for i in range(4):
        if ops[i]:
            ops[i] -= 1
            if i == 0:
                dfs(depth + 1, result + nums[depth])
            elif i == 1:
                dfs(depth + 1, result - nums[depth])
            elif i == 2:
                dfs(depth + 1, result * nums[depth])
            elif i == 3:
                dfs(depth + 1, int(result / nums[depth]))
            ops[i] += 1;  #원상복구

dfs(1, nums[0])
print(max_value)
print(min_value)

구현 코드(Java) 👇

import java.util.Scanner;
import java.lang.Math;

public class Main {
	static int N;
	static int[] nums;
	static int[] ops = new int[4];
	static Integer max_value = Integer.MIN_VALUE, min_value = Integer.MAX_VALUE;
	
	public static void dfs(int depth, int result) {
		if(depth == N) {
			max_value = Math.max(max_value, result);
			min_value = Math.min(min_value, result);
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			if(ops[i] != 0) {
				ops[i]--;
				switch (i) {
				
				case 0: dfs(depth + 1, result + nums[depth]); break;
				case 1: dfs(depth + 1, result - nums[depth]); break;
				case 2: dfs(depth + 1, result * nums[depth]); break;
				case 3: dfs(depth + 1, result / nums[depth]); break;
				
				}
				ops[i]++;   // 원상태로 복구
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		nums = new int[N];
		for(int i = 0; i < N; i ++) {
			nums[i] = sc.nextInt();
		}
		
		for(int i = 0; i < 4 ; i ++) {
			ops[i] = sc.nextInt();
		}
		
		dfs(1, nums[0]);
		System.out.println(max_value);
		System.out.println(min_value);
		
	}

}