[백준 14888번 C++] 연산자 끼워넣기

1. 문제 링크

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

 

 

2. 문제 설명

N개의 수와 N-1개의 연산자를 입력받은 후 만들 수 있는 식의 결과의 최댓값과 최솟값을 출력하는 문제입니다.

주어진 수의 순서를 바꾸면 안 되고, 식의 계산은 연산자 우선순위를 무시하고 왼쪽에서 오른쪽으로 진행해야 합니다.

따라서 연산자로 순열을 만들고 모든 경우의 수에 대하여 계산해보면 됩니다.

 

 

 

3. 소스코드

BOJ 14888번 연산자 끼워넣기 C++ 풀이입니다.

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, temp, min_result = 1000000000, max_result = -100000000;
	vector<int> v, op;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		v.push_back(temp);
	}
	for (int i = 0; i < 4; i++) {
		cin >> temp;
		for (int j = 0; j < temp; j++)
			op.push_back(i);
	}

	do {
		int result = v[0];
		for (int i = 0; i < N - 1; i++) {
			if (op[i] == 0)
				result += v[i + 1];
			else if (op[i] == 1)
				result -= v[i + 1];
			else if (op[i] == 2)
				result *= v[i + 1];
			else if (op[i] == 3)
				result /= v[i + 1];
		}
		min_result = min(min_result, result);
		max_result = max(max_result, result);
	} while (next_permutation(op.begin(), op.end()));
	cout << max_result << '\n' << min_result;

	return 0;
}

11번 라인 : 숫자의 개수 N, 임시로 사용할 변수 temp를 선언하고, 최솟값을 저장할 변수 min_result를 문제에서 주어진 최댓값인, 10억으로 초기화하고, 최댓값을 저장할 변수 max_result를 문제에서 주어진 최솟값인 -100으로 초기화합니다.

12번 라인 : 숫자를 저장할 vector v와 연산자를 저장할 vector op를 선언합니다.

13 ~ 17번 라인 : N과 v를 입력받습니다.

18 ~ 22번 라인 : op를 입력받습니다. 예를 들어 2, 1, 3, 1이 입력된다면 op vector에는 [0, 0, 1, 2, 2, 2, 3]이 입력되도록 이중 for문을 사용했습니다.

24, 38번 라인 : do ~ while문과 next_permutation을 이용해서 op vector로 만든 순열의 모든 경우의 수를 차례로 구합니다.

25번 라인 : 계산 결과를 저장할 result변수를 v[0](첫 번째 숫자)로 초기화합니다.

26 ~ 35번 라인 : i번째 op의 값에 따라 해당하는 연산자를 이용하여 result와 v[i + 1]을 연산합니다.

36번 라인 : min_result와 result값을 비교하여 더 작은 값을 min_result에 저장합니다.

37번 라인 : max_result와 result값을 비교하여 더 큰 값을 max_result에 저장합니다.

39번 라인 : max_result와 min_result를 출력합니다.