백준 14888번 연산자 끼워넣기

- 문제 설명

 

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

 

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다.

 

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하시오

 

 

- 입력

 

1) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다.

 

2) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100)

 

3) 셋째 줄에는 합이 N-1인 4개의 정수가 주어진다. (차례로 +, -, ×, ÷ 의 개수이다.)

 

 

- 출력

 

1) 첫째 줄에 만들 수 있는 식의 결과의 최댓값 출력

 

2) 둘째 줄에는 최솟값을 출력

 

> 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다.

 

> 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

 

* 문제 풀이의 핵심

 

 

1. 브루트포스

 

이 문제는 N개의 수 사이에 들어갈 수 있는 연산자의 순서를 순열로 모두 구하는 문제로 바꿀 수 있습니다.

 

(+, -, ×, ÷ 를 0, 1, 2, 3 으로 치환하여 순열을 구할 수 있습니다.)

 

브루트포스 문제는 순열의 구해야 하는 수가 모든 순열을 구하는 시간복잡도가 O(N!*N) 이기 때문에, 수의 개수가 10개 이하일 때 1초인 시간제한 내에 풀 수 있다고 볼 수 있습니다.

 

이 문제는 N이 최대 11이며, 연산자의 개수는 N-1 개 이므로 브루트포스로 시간제한 이내에 풀 수 있는 문제입니다.

 

* 1초 연산 : 1억번이라고 가정

 

 

2. 알고리즘 (순열)

 

0) 최댓값, 최솟값 초기값 설정

 

> 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다.

 

> 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

위 두가지 조건을 만족시키기 위해서, 중간식의 결과가 int형의 범위를 넘지 않으며, 최대 값은 -10억보다 작은수, 최소 값은 10억 보다 큰 수로 설정하면 됩니다.

 

int maxValue = -2100000000;
int minValue = 2100000000;

 

 

1) 연산자 치환하기

 

셋째 줄에서 입력받은 값을 operators 라는 배열에 저장시킨 후 연산자를 0~4 의 정수 값으로 치환시킵니다.

 

치환할 때, 연산자의 개수만큼 0~4 정수를 추가하여야 올바르게 모든 순열을 구할 수 있습니다.

 

vector<int> combination;
for (i = 0; i < 4; i++) {
  if (operators[i] > 0) {
    for (j = 0; j < operators[i]; j++) {
    	combination.push_back(i);
    }
  }
}

 

 

2) 모든 경우의 수 찾기 (순열)

 

- C++ STL의 next_permutation 을 사용하면 모든 순열을 구할 수 있습니다.

 

(next_permutation을 사용하기 전에 수가 모두 오름차순 정렬되어 있어야 모든 경우의 수를 구할 수 있습니다.)

 

- 순열을 구할 때 마다 연산자 배열에 따른 결과 값을 계산한 뒤 정답을 갱신해야 합니다.

 

sort(combination.begin(), combination.end());

do {
  int ret = calc(combination, N);
  if (maxValue < ret) maxValue = ret;
  if (minValue > ret) minValue = ret;

} while (next_permutation(combination.begin(), combination.end()));

 

 

3) 연산자 배열에 따른 결과 값 계산

 

- '식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.' 는 조건에 따라서, 차례로 모든 값을 계산해 주면 결과를 얻을 수 있습니다.

 

- 음수 나눗셈 계산시 C++ 언어를 사용한다면 그냥 / 연산을 사용하면 문제의 조건에 일치하는 결과 값이 나온다.

 

int calc(vector<int> c, int n) {
	int ret = A[0];

	int i;
	for (i = 1; i < n; i++) {
		if (c[i - 1] == 0) ret += A[i];
		if (c[i - 1] == 1) ret -= A[i];
		if (c[i - 1] == 2) ret *= A[i];
		if (c[i - 1] == 3) ret /= A[i];
	}

	return ret;
}

 

 

- 소스코드

 

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

using namespace std;

int A[101];
// 0 : +, 1 : -, 2 : *, 3 : /
int operators[4];

int maxValue = -2100000000;
int minValue = 2100000000;

int calc(vector<int> c, int n) {
	int ret = A[0];

	int i;
	for (i = 1; i < n; i++) {
		if (c[i - 1] == 0) ret += A[i];
		if (c[i - 1] == 1) ret -= A[i];
		if (c[i - 1] == 2) ret *= A[i];
		if (c[i - 1] == 3) ret /= A[i];
	}

	return ret;
}

int main() {
	int N;
	cin >> N;

	int i, j;
	for (i = 0; i < N; i++) {
		cin >> A[i];
	}

	for (i = 0; i < 4; i++) {
		cin >> operators[i];
	}

	vector<int> combination;
	for (i = 0; i < 4; i++) {
		if (operators[i] > 0) {
			for (j = 0; j < operators[i]; j++) {
				combination.push_back(i);
			}
		}
	}
	sort(combination.begin(), combination.end());

	do {
		int ret = calc(combination, N);
		if (maxValue < ret) maxValue = ret;
		if (minValue > ret) minValue = ret;

	} while (next_permutation(combination.begin(), combination.end()));

	cout << maxValue << "\n";
	cout << minValue << "\n";
}

 

 

 

- 문제링크 : www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

 

- 제출한 코드

 

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요