[백준 14888] 연산자 끼워넣기(C++, Java)

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

문제해설

• 숫자 사이사이에 연산자를 끼워넣는 느낌.
• 그러기 위해서는 DFS로 구현
  • ex) 연산자가 1 0 1 0 이라고 가정하고 List에 두가지 경우 0, 2와 2, 0경우를 재귀로 돌린다.
  • 0, 2의 경우 3 [0] 4 [2] 5 -->0은 더하기, 2는 곱하기 max or min을 구한다.
  • 2, 0의 경우 3 [2] 4 [0] 5 --> "

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int map[11];
int vi[4];
int ar[4];
int resmax = -1000000001, resmin = 1000000001, n;
vector<int> v;

void input()
{
   cin >> n;
   for (int i = 0; i < n; i++)
      cin >> map[i];
   for (int i = 0; i < 4; i++)
      cin >> ar[i];
}

void pro(int ct)
{
   if (ct == n - 1)
   {
      int S = map[0];
      for (int i = 0; i < v.size(); i++)
      {
         if (v[i] == 0)
            S += map[i + 1];
         else if (v[i] == 1)
            S -= map[i + 1];
         else if (v[i] == 2)
            S *= map[i + 1];
         else if (v[i] == 3)
            S /= map[i + 1];
      }
      resmax = max(resmax, S);
      resmin = min(resmin, S);
      return;
   }

   for (int w = 0; w < 4; w++)
   {
      if (ar[w] == 0)
         continue;
      if (vi[w] < ar[w])
      {
         vi[w]++;
         v.push_back(w);
         pro(ct + 1);
         v.pop_back();
         vi[w]--;
      }
   }
}

int main()
{
   input();
   pro(0);
   cout << resmax << endl << resmin << endl;
   return 0;
}

 

Java

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int numbers[];
	static int count[] = new int[4];
	static int visited[];
	static ArrayList<Integer> comb = new ArrayList<Integer>();
	static int max = -1000000001;
	static int min = 1000000001;

	// static int result_max;
	// static int result_min;
	static void pro(int ct) {
		if (ct == N - 1) {
			// System.out.println(comb);
			int sum = numbers[0];
			for (int i = 0; i < comb.size(); i++) {
				if (comb.get(i) == 0) {
					sum += numbers[i + 1];
				} else if (comb.get(i) == 1) {
					sum -= numbers[i + 1];
				} else if (comb.get(i) == 2) {
					sum *= numbers[i + 1];
				} else if (comb.get(i) == 3) {
					sum /= numbers[i + 1];
				}
			}
			// System.out.println(sum);
			max = Math.max(sum, max);
			min = Math.min(sum, min);

		}
		for (int i = 0; i < 4; i++) {
			if (count[i] == 0)
				continue;
			if (visited[i] != count[i]) {
				visited[i]++;
				comb.add(i);
				pro(ct + 1);
				// System.out.println(comb);
				comb.remove(comb.size() - 1);
				visited[i]--;
			}
		}
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		numbers = new int[N];
		// 0: + 1:- 2: x 3: /
		visited = new int[4];
		Arrays.fill(visited, 0);
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		for (int i = 0; i < N; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		input = br.readLine();
		st = new StringTokenizer(input);
		for (int i = 0; i < 4; i++) {
			count[i] = Integer.parseInt(st.nextToken());
		}
		pro(0);
		System.out.println(max);
		System.out.println(min);
	}

}