[ 백준 ] 14888번 : 연산자 끼워넣기 - ( C++/C , PYTHON/파이썬, JAVA/자바 )

• 문제

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

14888번: 연산자 끼워넣기

---

• 풀이법 ( 알고리즘 )

재귀적인 방법을 사용하여 풀 수 있다. 각 수에 대해 연산의 경우의 수를 고려하여 풀 수 있었다. 

재귀함수는 생각보다 구현이 어렵게 느껴진다.

---

• 풀이 - C++ ( C )

#include <iostream>
#include <algorithm>
#define MAX 1000000000 + 1

using namespace std;

int n, P, M, MT, D, maxResult = -MAX, minResult = MAX; // n : 수의 개수 , P : 덧셈 연산자의 개수 , M : 뺄셈 연산자의 개수 , MT : 곱셈의 개수 , D : 나눗셈의 개수 . maxResult : 가장 큰 값 , minResult : 가장 작은 값
int A[11]; // A[x] : 식의 수

void solution(int idx, int sum, int plus, int minus, int multiply, int divide) // idx : 현재 가르키는 수의 인덱스 , sum : 현재까지의 값
{
	if (idx == n) //모든 연산자 사용
	{
		maxResult = max(maxResult, sum); //최댓값 갱신
		minResult = min(minResult, sum); //최솟값 갱신
	}
	 
	
	if (plus > 0) // 덧셈 연산자를 사용할 수 있다면
		solution(idx + 1, sum + A[idx], plus - 1, minus, multiply, divide); //덧셈연산자를 사용할 수 있는 횟수를 1 감소, 현재까지 합에 다음 수를 더한 상태로 함수 실행
	if(minus > 0) // 뺄셈 연산자를 사용할 수 있다면
		solution(idx + 1, sum - A[idx], plus, minus - 1, multiply, divide); // 뺄셈 연산자를 사용할 수 있는 횟수를 1 감소, 현재까지 합에 다음 수를 뺀 상태로 함수 실행
	if(multiply > 0) // 곱셈 연산자를 사용할 수 있다면
		solution(idx + 1, sum * A[idx], plus, minus, multiply - 1, divide); // 곱셈 연산자를 사용할 수 있는 횟수를 1 감소, 현재까지 합에 다음 수를 곱한 상태로 함수 실행
	if(divide > 0) // 나눗셈 연산자를 사용할 수 있다면
		solution(idx + 1, sum / A[idx], plus, minus, multiply, divide - 1); // 나눗셈 연산자를 사용할 수 있는 횟수를 1 감소, 현재까지 합에 다음 수를 나눈 상태로 함수 실행
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//input
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> A[i];
	cin >> P >> M >> MT >> D;

	//solve
	solution(1, A[0], P, M, MT, D); // 2번째, 즉 A[1]번부터 연산을 시작하므로 idx의 초깃값은 1, sum은 A[0]부터,  입력받은 각 연산자들의 수를 초깃값으로 함수 실행

	//output
	cout << maxResult << "\n";
	cout << minResult;

	return 0;
}

• 풀이 - JAVA

import java.util.*;

public class Main {
	static int[] A = new int[11];
	static int n, pls, mns, mt, div;
	static int maxResult = -1000000000, minResult = 1000000000;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		 n = sc.nextInt();
		
		for(int i = 0; i < n; i++)
			A[i] = sc.nextInt();
		
		pls = sc.nextInt();
		mns = sc.nextInt();
		mt = sc.nextInt();
		div = sc.nextInt();
		
		solution(1, A[0], pls,mns,mt,div);
		
		System.out.println(maxResult);
		System.out.println(minResult);
	}
	
	public static void solution(int idx, int sum, int plus, int minus, int multiply, int divide)
	{
		if(idx == n) 
		{
			maxResult = Math.max(maxResult, sum);
			minResult = Math.min(minResult, sum);
		}
		
		if(plus > 0) solution(idx +1, sum + A[idx], plus - 1, minus, multiply, divide);
		if(minus > 0) solution(idx +1, sum - A[idx], plus, minus - 1, multiply, divide);
		if(multiply > 0) solution(idx +1, sum * A[idx], plus, minus, multiply- 1, divide);
		if(divide > 0) solution(idx +1, sum / A[idx], plus, minus, multiply, divide - 1);
	}
}

• 풀이 - PYTHON

n = int(input())
A = []

max_result = -1000000000
min_result = 1000000000

A = list(map(int, input().split()))

plus,minus,multiply,divide = map(int, input().split())

def solution(cnt, sum):
    global plus, minus, multiply, divide, max_result, min_result
    if cnt == n: 
        max_result = max(max_result, sum)
        min_result = min(min_result, sum)
    else:
        if plus > 0:
            plus -= 1
            solution(cnt + 1, sum + A[cnt])
            plus += 1
        if minus > 0:
            minus -= 1
            solution(cnt + 1, sum - A[cnt])
            minus += 1
        if multiply > 0:
            multiply -= 1
            solution(cnt + 1, sum * A[cnt])
            multiply += 1
        if divide > 0:
            divide -= 1
            solution(cnt + 1, int(sum / A[cnt]))
            divide += 1



solution(1,A[0])

print(max_result)
print(min_result)