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

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

14888번: 연산자 끼워넣기

 

처음에 연산자가 아닌 수들의 순서도 바뀔 수 있는줄 알고 푸는 방법을 생각해내는데 애를 먹었었다.

 

하지만 나중에 수들의 순서는 고정된 것을 알아채고, 연산자의 순서만 바뀐다는 것을 알고 해결방법을 쉽게 생각해낼 수 있었다.

 

 

만약 수들이 모여 있고, 이 수들의 모든 경우의 수를 구하고 싶다면 next_permutation을 사용해 구할 수 있다.

이 next_permutation으로 연산자의 배열을 매번 다르게 해 값들을 구한 다음에 최소 값과 최대 값으로 저장해주면 쉽게 풀림을 알 수 있다.

 

• next_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.
• prev_permutation : 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환.

참고 : https://twpower.github.io/82-next_permutation-and-prev_permutation

 

구현 코드

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

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> numbers;
	for (int i = 0; i < N; ++i) {
		int tmp;
		cin >> tmp;
		numbers.push_back(tmp);
	}

	vector<char> op;
	for (int i = 0; i < 4; ++i) {
		int tmp;
		cin >> tmp;

		for (int j = 0; j < tmp; j++) {
			if (i == 0) {
				op.push_back(0);
			}
			else if (i == 1) {
				op.push_back(1);
			}
			else if (i == 2) {
				op.push_back(2);
			}
			else if (i == 3) {
				op.push_back(3);
			}
		}
	}

	int minNum = 1000000000;
	int maxNum = -1000000000;

	do {


		int idx = 0;
		int res = numbers[idx];
		for (int i = 0; i < N - 1; ++i) {
			if (op[i] == 0) res += numbers[++idx];
			else if (op[i] == 1) res -= numbers[++idx];
			else if (op[i] == 2) res *= numbers[++idx];
			else if (op[i] == 3) { 
				if (numbers[idx] < 0) {
					res *= -1;
					res /= numbers[++idx];
					res *= -1;
				}
				else res /= numbers[++idx];
			}
		}

		minNum = min(minNum, res);
		maxNum = max(maxNum, res);


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

	cout << maxNum << endl;
	cout << minNum;
}

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!