문제

BOJ 14888, 연산자 끼워넣기

핵심

• 입력의 크기가 $10$이라 구현에 초점을 맞춘다.
• n개의 수가 주어지고, 사칙연산 연산자가 n-1개 주어진다. 연산자를 끼워 넣었을 때 만들 수 있는 최댓값과 최솟값을 출력하는 문제이다.
• 가능한 연산자 순서를 구하기 위한 순열을 생성한다. 만약 연산자가 +, +, -, *, / 라면
  +, +, -, *, / 를 두 번 선택하는 경우를 막기 위해 중복 순열을 제거한다.
• +, -, *, / 연산자를 입력받을 때 0, 1, 2, 3으로 입력을 받는다. 예를 들어 + + - * / 라면 0 0 1 2 3의 순열이 생성된다. 해당 연산자 순열이 만들어졌으면 이를 피연산자에 하나씩 적용하여 최댓값과 최솟값을 구할 수 있다.

개선

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int a[14];
vector<int> oper;
int n;
int mx = -1e9;
int mn = 1e9;
void dfs(int depth, vector<int>& seq, vector<bool> isSelected) {
	if (depth == n - 1) { 
		int result = a[0];
		for (int i = 1; i < n; ++i) {
			if (seq[i - 1] == 0)
				result += a[i];
			else if (seq[i - 1] == 1)
				result -= a[i];
            else if (seq[i - 1] == 2)
				result *= a[i];
            else if (seq[i - 1] == 3)
				result /= a[i];
		}
		mx = max(mx, result);
		mn = min(mn, result);
	}
	int prev = -1;
	for (int i = 0; i < (int)oper.size(); ++i) {
    	// 이미 선택되었거나 이전과 같은 연산자가 있다면 선택하지 않는다.
		if (isSelected[i] || (prev != -1 && oper[i] == oper[prev])) 
			continue;
		isSelected[i] = true;
		seq.push_back(oper[i]);
		dfs(depth + 1, seq, isSelected);
		seq.pop_back();
		isSelected[i] = false;
		prev = i;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 0 ; i < 4; ++i) {
		int cnt;
		cin >> cnt;
		for (int j = 0; j < cnt; ++j)
			oper.push_back(i);
	}
	vector<int> seq;
	vector<bool> isSelected(oper.size(), false);
	dfs(0, seq, isSelected);
	cout << mx << '\n' << mn;
}

• 가능한 모든 순열을 생성한 뒤 이 순열을 하나씩 계산하는 방법이다. 하지만, dfs를 호출하면서 순열을 생성함과 동시에 계산할 수 있다. 사용할 수 없는 연산자가 없다면 건너뛰는 방식으로 좀 더 효율적인 구현이 가능하다. 해당 코드는 아래에 소개하였다.

코드

시간복잡도

• 대략 $O(4^{n - 1})$

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int a[14];
int oper[4];
int n;
int mx = -1e9;
int mn = 1e9;
void dfs(int depth, int sum) {
	if (depth == n) {
		mx = max(mx, sum);
		mn = min(mn, sum);
	}
	for (int i = 0; i < 4; ++i) {
		if (oper[i] == 0)
			continue;
		oper[i]--;
		if (i == 0)
			dfs(depth + 1, sum + a[depth]);
		else if (i == 1)
			dfs(depth + 1, sum - a[depth]);
		else if (i == 2)
			dfs(depth + 1, sum * a[depth]);
		else
			dfs(depth + 1, sum / a[depth]);
		oper[i]++;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 0 ; i < 4; ++i)
		cin >> oper[i];
	dfs(1, a[0]);
	cout << mx << '\n' << mn;
}

Java

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

public class Main {
    static int n;
    static int[] a = new int[14];
    static int[] oper = {0, 0, 0, 0};
    static int mx = Integer.MIN_VALUE;
    static int mn = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++)
            oper[i] = Integer.parseInt(st.nextToken());
        dfs(1, a[0]);
        System.out.println(mx);
        System.out.println(mn);
        br.close();
    }

    static void dfs(int depth, int sum) {
        if (depth == n) {
            mx = Math.max(mx, sum);
            mn = Math.min(mn, sum);
        }
        for (int i = 0; i < 4; ++i) {
            if (oper[i] == 0)
                continue;
            --oper[i];
            if (i == 0)
                dfs(depth + 1, sum + a[depth]);
            else if (i == 1)
                dfs(depth + 1, sum - a[depth]);
            else if (i == 2)
                dfs(depth + 1, sum * a[depth]);
            else
                dfs(depth + 1, sum / a[depth]);
            ++oper[i];
        }
    }
}