[백준 14888번] 연산자 끼워넣기 (순열)

본 포스팅에서는 삼성 SW 역량테스트 기출문제 중 순열 유형을 풀어 보려고 합니다. 백준 14888번 연산자 끼워넣기 문제입니다. 특별한 응용은 없는 기본적인 순열의 문제라고 보시면 됩니다. 순열 알고리즘 포스팅에서 말씀드린 것처럼 STL를 사용하여 순열을 사용하셔도 상관없습니다.

 

2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 14888번] 연산자 끼워넣기 (순열)

2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 15686번] 치킨배달 (조합)

2021.04.14 - [알고리즘/SW역량테스트 기출문제] - [백준 14889번] 스타트와 링크 (조합)

2021.04.18 - [알고리즘/SW역량테스트 기출문제] - [백준 15683번] 감시 (조합)

2021.04.20 - [알고리즘/SW역량테스트 기출문제] - [백준 14501번] 퇴사 (조합)

 

안녕하세요. 지칸입니다.

오늘은 기본적인 순열 문제를 풀이해보려고 합니다. 백준 14888번의 연산자 끼워넣기 문제입니다. 별다른 응용 없이 문제만 제대로 이해했다면 순열을 통해 정답을 도출할 수 있습니다.

 

1) 문제 이해

2) 구조 잡기

3) STL을 사용한 문제 풀이

 

저의 결론) 기본적인 순열문제입니다. STL를 사용한다면 더욱 간단하게 구현할 수 있습니다.

---

1) 문제 이해

문제 출처 : www.acmicpc.net/problem/14888

 

문제)

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

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4 × 5÷6
• 1÷2+3+4-5 × 6
• 1+2÷3 ×4-5+6
• 1÷2 × 3-4+5+6

식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4 × 5÷6 = 1
• 1÷2+3+4-5 × 6 = 12
• 1+2÷3 ×4-5+6 = 5
• 1÷2 × 3-4+5+6 = 7

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

 

-> 문제 해석

• N개의 수, N-1개의 연산자, 각각의 배열이 필요
• 연산자 N-1개를 순서를 바꿔가며 순서를 정함 -> 순열
• N개의 순서는 변하지 않음
• 모든 경우에 대해 최대, 최소를 비교하며 저장

입력)

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2,...,2 AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

 

-> 입력 해석

• MAX_N = 11
• 덧셈, 뺄셈, 곱셈, 나눗셈 순

출력)

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워 넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

-> 출력 해석

• 변수의 타입이 커야 한다. longlong 타입으로 결정
• 최댓값, 최솟값을 모든 경우의 수에 대해 비교하여 저장

---

2) 구조 잡기

시작은 동일합니다. 기본적인 틀을 준비합니다.

2019.04.25 - [알고리즘/SW역량테스트] - (1장-1) 역량 테스트 기본 템플릿 준비

2-1) 초기 세팅

input을 받을 수 있는 코드를 넣어줍니다. 그리고 연산자의 개수를 순서대로 받아서 arr 배열에 그 개수만큼 추가해 줍니다. 순열을 하기 위한 후보 집합이기 때문에 초기에 arr배열에 넣어주는 건 순서가 의미 없습니다. 

#include <iostream>
#include <vector>
using namespace std;
#define INF 123456789;
#define MAX_N 11
#define ADD 0
#define SUB 1
#define MUL 2
#define DIV 3
int N;
int list[MAX_N];
vector<int> arr;	

long long Max_num = -INF;
long long Min_num = INF;

int main() {
	cin >> N;
	int temp;
	for (int i = 0; i < N; i++) {		
		cin >> temp;
		list[i] = temp;
	}
	for (int i = 0; i < 4; i++) { // 0덧셈 1뺄셈 2곱셈 3나눗셈
		cin >> temp;
		for (int j = 0; j < temp; j++) {
			arr.push_back(i); //각 연산자의 개수만큼 넣기 
		}
	}
	
    // 순열 동작
    
	cout << Max_num << endl;
	cout << Min_num << endl;
	return 0;
}

 

2-2) 순열 구현하기

순열 알고리즘 포스팅의 내용과 다른 게 없습니다. 조합/순열의 경우 모든 구조는 똑같고 어떤 동작을 할 것인지만 차이점이 존재합니다.

2021.03.31 - [알고리즘/SW역량테스트] - (4장-1) 순열(Permutation)알고리즘이란?

void swap(int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

void perm(int depth, int n, int k) {
	if (depth == k) {
		operation();
		return;
	}
	for (int i = depth; i < n; i++) {
		swap(i, depth);
		perm(depth + 1, n, k);
		swap(i, depth);
	}
}

순열 알고리즘 자체에 대한 설명은 위 포스팅에서 다루고 있으니 생략하겠습니다. 우리는 operation 함수만 문제에 맞도록 수정하면 됩니다.

 

2-3) 연산 결과 구현하기

하나의 경우의 수를 찾았을 때의 동작을 구현한 코드입니다. 별다른 내용은 없고 숫자와 연산자 배열을 하나씩 보면서 연산하면 됩니다.

void operation() {
	long long temp = list[0];
	for (int i = 0; i < N - 1; i++) {
		if (arr[i] == ADD) temp = temp + list[i + 1];
		else if (arr[i] == SUB) temp = temp - list[i + 1];
		else if (arr[i] == MUL) temp = temp * list[i + 1];
		else if (arr[i] == DIV) temp = temp / list[i + 1];
	}
	if (Max_num < temp) Max_num = temp;
	if (Min_num > temp) Min_num = temp;
}

---

3) STL을 사용한 문제 풀이

STL을 사용하여 순열을 풀이해보면 큰 차이는 없지만 perm함수를 직접 구현하지 않아도 되니 간편할 수 있습니다. 우리는 operation 함수만 구현하고 while문을 입력하여 똑같은 결과를 얻을 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 123456789;
#define MAX_N 11
#define ADD 0
#define SUB 1
#define MUL 2
#define DIV 3
int N;
int list[MAX_N];
vector<int> arr;	

long long Max_num = -INF;
long long Min_num = INF;
void operation() {
	long long temp = list[0];
	for (int i = 0; i < N - 1; i++) {
		if (arr[i] == ADD) temp = temp + list[i + 1];
		else if (arr[i] == SUB) temp = temp - list[i + 1];
		else if (arr[i] == MUL) temp = temp * list[i + 1];
		else if (arr[i] == DIV) temp = temp / list[i + 1];
	}
	if (Max_num < temp) Max_num = temp;
	if (Min_num > temp) Min_num = temp;
}

int main() {
	cin >> N;
	int temp;
	for (int i = 0; i < N; i++) {		
		cin >> temp;
		list[i] = temp;
	}
	for (int i = 0; i < 4; i++) { // 0덧셈 1뺄셈 2곱셈 3나눗셈
		cin >> temp;
		for (int j = 0; j < temp; j++) {
			arr.push_back(i); //각 연산자의 개수만큼 넣기 
		}
	}

	operation();	
	while (next_permutation(arr.begin(), arr.end())) {
		operation();
	}

	cout << Max_num << endl;
	cout << Min_num << endl;
	return 0;
}