1) 문제 분석
N개의 정수 사이에 N-1개의 연산자를 배치하는데, 이 때의 최댓값/최솟값을 구하여 출력한다.
이 문제의 핵심은 ‘숫자들의 순서가 바뀌지 않는다’인 것 같다. 처음에는 이 점을 생각 못하고 수를 오름차순으로 정리하여 최댓값을 구하는 방법을 생각했는데 문제를 다시 읽고 그렇게 풀이해서는 안 된다는 것을 깨달았다.
물론 모든 경우의 수를 따져서 최대와 최소를 구할 수 있지만, 그보다 더 효율적인 방법이 없는지 좀 더 고민해보고 싶었다. 그런데 수가 정렬되어 있지 않고 무작위로 있기 때문에 더 나은 방법이 없을거라는 생각이 들어서 우선 모든 경우의 수를 구해보는 방법을 시도해보기로 하였다(수의 개수가 최대 11개 밖에 되지 않기 때문에).
2-1) 알고리즘-첫 번째 시도
일단 가능한 모든 순열을 찾아야 하는데, 이럴 때 보통 재귀함수를 사용하는 것 같다.
op_rec라는 함수가 그 역할을 하는데, parameter로 현재 벡터에 들어가있는 연산자의 개수를 받는다. 만약 모든 연산자가 벡터에 있다면 하나의 순열이 완성된 것이므로, 벡터에 저장된 순서대로 연산자를 뽑아내서 식을 계산해주고 이를 현재 최솟값/최댓값과 비교해주고 업데이트하면 된다.
parameter의 값이 연산자의 총 개수와 같지 않다면, 아직 순열이 완성되지 않은 것이므로, 아직 포함되지 않은 연산자들 중 하나를 골라 벡터의 마지막에 추가하고, 자기 자신을 호출하여 그 다음에 올 연산자를 고르도록 한다.
이 때, in이라는 배열을 사용하여, i번째 연산자가 현재 순열에 포함되어있는지 아닌지를 알려주도록 한다. 따라서, 자기 자신을 호출하기 전에는, i번째 연산자가 방금 순열에 포함되었으므로, in[i]의 값이 true가 되어서 재귀함수 안에서 이 연산자는 고려되지 않는다. 호출한 함수가 끝나면, in[i]의 값을 다시 false로 설정하고, 다음 연산자가 뽑혔을 때 마찬가지로 자기 자신을 호출하면, i번째 연산자는 아직 순열에 없기 때문에 고려 대상이 된다. 이런식으로 모든 순열을 구할 수 있다.
2-2) 코드-첫 번째 시도
1.재귀함수
/**
* N integers and N-1 arithmetic operators(+,-,*,/) are given.
* While the sequence of the integers remains the same,
* find the max and min values of expressions that can be created by permutation of the operators
*
* intput: number of integers
* a sequence of integers
* number of each operator (in order of +,-,*,/)
* output: max value
* min value
*/
#include <iostream>
#include <vector>
using namespace std;
//oprators
enum op{plus=0, minus=1, mult=2, divs=3};
int operators[10]; //number of each operator
bool in[10]; //true if the operator is already chosen
int numbers[11]; //a sequence of integers
int N; //total number of integers
int res_min; //minimum value
int res_max; //maximum value
vector<int> op_q; //permutation of operators
//find every permutation recursively
void op_rec(int m){
//one new permutation created
if(m==N-1){
int op; //operator
int i = 1; //loop variable for integer values
int total = numbers[0]; //first integer in the expression
//cout<<numbers[0];
//calculate the value of the expression
for(int k=0; k<N-1; k++){
op = op_q[k];
switch (op){
case op::plus:
//cout<<"+"<<numbers[i];
total += numbers[i++];
break;
case op::minus:
//cout<<"-"<<numbers[i];
total -= numbers[i++];
break;
case op::mult:
//cout<<"*"<<numbers[i];
total *= numbers[i++];
break;
case op::divs:
//cout<<"/"<<numbers[i];
total /= numbers[i++];
break;
}
}
//cout<<"\n";
//check if the value is min or max
if(total<res_min)
res_min = total;
if(total>res_max)
res_max = total;
}
//keep creating new permutation
else{
for(int i=0; i<N-1; i++){
//choose an operator that comes next
if(!in[i]) {
in[i] = true;
op_q.push_back(operators[i]);
//choose next operator
op_rec(m+1);
//operators[i] is not chosen
in[i] = false;
op_q.pop_back();
}
}
}
}
int main(){
cin >> N; //number of integers
//get N integers from input
for(int i=0; i<N; i++)
cin >> numbers[i];
//get number of operators
int index=0;
for(int i=0; i<4; i++) {
int n;
cin >> n;
//create an array of operators
for(int j=0; j<n; j++)
operators[index++] = i;
}
//initialize
for(int i=0; i<N-1; i++)
in[i] = false;
res_min = INT32_MAX;
res_max = INT32_MIN;
//find every permutation and compare the values to find min/max values
op_rec(0);
//print out the result
cout<<res_max<<"\n"<<res_min;
}
그런데 이 문제에서는 연산자의 종류가 4가지이며 한 종류의 연산자가 여러 개 있을 수 있으므로 중복되는 순열이 생길 수 있다. 실제로 내 코드는 300ms 정도의 시간이 걸렸는데, 다른 사람들의 결과를 보면 대부분 0ms 이하로 걸린 것을 확인할 수 있었다. 심지어 코드 길이도 훨씬 더 짧다!
3-1) 알고리즘-두 번째 시도: 벡터 사용하지 않기
알고리즘은 같지만 이번에는 벡터에 연산자들을 저장하고 마지막에 처음부터 일일히 계산해주는 대신, 재귀함수를 호출하기 전에 선택한 연산자를 사용하여 값을 계산하고 그 값을 파라미터로 넘겨주도록 하였다. 이렇게 되면 벡터를 사용할 필요가 없어진다. 여기서 중요한 점은 재귀함수 호출 전 값을 계산할 때 원래 값이 바껴서 재귀함수가 끝나고 리턴해서 다른 수열을 만들 때 값이 이상해지지 않도록 새로운 변수에 값을 계산해서 넘겨주는 것이다. temp가 그 역할을 한다.
3-2) 코드-두 번째 시도: 벡터 사용하지 않기
시간이 거의 절반인 160ms로 줄었다!
/**
* N integers and N-1 arithmetic operators(+,-,*,/) are given.
* While the sequence of the integers remains the same,
* find the max and min values of expressions that can be created by permutation of the operators
*
* intput: number of integers
* a sequence of integers
* number of each operator (in order of +,-,*,/)
* output: max value
* min value
*/
#include <iostream>
#include <vector>
using namespace std;
//oprators
enum op{plus=0, minus=1, mult=2, divs=3};
int operators[10]; //number of each operator
bool in[10]; //true if the operator is already chosen
int numbers[11]; //a sequence of integers
int N; //total number of integers
int res_min; //minimum value
int res_max; //maximum value
//find every permutation recursively
void op_rec(int m, int value){
//one new permutation created
if(m==N-1){
//check if the value is min or max
if(value<res_min)
res_min = value;
if(value>res_max)
res_max = value;
}
//keep creating new permutation
else{
for(int i=0; i<N-1; i++){
//choose an operator that comes next and calculate the value
if(!in[i]) {
in[i] = true; //operator[i] is chosen
//save the value
int temp = value;
switch (operators[i]){
case op::plus:
temp += numbers[m+1];
break;
case op::minus:
temp -= numbers[m+1];
break;
case op::mult:
temp *= numbers[m+1];
break;
case op::divs:
temp /= numbers[m+1];
break;
}
//choose next operator
op_rec(m+1, temp);
//operators[i] is not chosen
in[i] = false;
}
}
}
}
int main(){
cin >> N; //number of integers
//get N integers from input
for(int i=0; i<N; i++)
cin >> numbers[i];
//get number of operators
int index=0;
for(int i=0; i<4; i++) {
int n;
cin >> n;
//create an array of operators
for(int j=0; j<n; j++)
operators[index++] = i;
}
//initialize
for(int i=0; i<N-1; i++)
in[i] = false;
res_min = INT32_MAX;
res_max = INT32_MIN;
//find every permutation and compare the values to find min/max values
op_rec(0, numbers[0]);
//print out the result
cout<<res_max<<"\n"<<res_min;
}
4-1) 알고리즘-세 번째 시도: 중복되는 순열 건너뛰기
그래도 아직 0ms 아래로 시간이 획기적으로 줄지 않았기 때문에 좀 더 나은 방법을 생각해보기로 하였다.
4가지 연산자가 있고 각 연산자가 여러 개 있어서 똑같은 순열이 중복될 수 있기 때문에 모든 경우의 수를 구하는 것은 비효율적이다. 그래서 i번째 연산자를 선택할 때, 어떤 한 연산자가 i번째 오는 경우를 이미 재귀함수를 실행해서 구한 적이 있다면, 같은 연산자에 대해서는 고려하지 않고 건너뛰도록 하였다. 이 때 사용된 것이 chosen 배열인데, 길이가 4이며 op_rec 함수를 실행할 때 마다 전부 false로 초기화 된다.
예를 들어, else문 안의 for문에서 다음에 올 연산자를 선택할 때 ‘+’가 선택되었다면 chosen[0]의 값을 true로 설정한다. op_rec(m+1, temp) 함수가 리턴되고 다른 연산자들을 고려할 때, ‘+’가 오는 경우는 이미 op_rec(m+1, temp)에서 전부 계산했기 때문에 operators[i]가 ‘+’인 경우는 건너뛰면 시간을 절약할 수 있다. 처음에는 시간을 줄일려면 재귀 함수를 사용하지 말아야 했나 싶었는데 이런 경우의 수 문제에서는 계산 수를 줄이는 것만으로도 시간을 많이 줄일 수 있었다.
4-2) 코드-세 번째 시도: 중복되는 순열 건너뛰기
#include <iostream>
#include <vector>
using namespace std;
enum op{plus=0, minus=1, mult=2, divs=3};
int operators[10];
bool in[10];
int numbers[11];
int N, res_min, res_max;
void op_rec(int m, int value){
if(m==N-1){
if(value<res_min)
res_min = value;
if(value>res_max)
res_max = value;
}
else{
bool chosen[4];
for(int i=0; i<4; i++)
chosen[i] = false;
for(int i=0; i<N-1; i++){
if(!in[i] && !chosen[operators[i]]) {
in[i] = true;
chosen[operators[i]] = true;
int temp = value;
switch (operators[i]){
case op::plus:
temp += numbers[m+1];
break;
case op::minus:
temp -= numbers[m+1];
break;
case op::mult:
temp *= numbers[m+1];
break;
case op::divs:
temp /= numbers[m+1];
break;
}
op_rec(m+1, temp);
in[i] = false;
}
}
}
}
int main(){
cin >> N;
for(int i=0; i<N; i++)
cin >> numbers[i];
int index=0;
for(int i=0; i<4; i++) {
int n;
cin >> n;
for(int j=0; j<n; j++)
operators[index++] = i;
}
for(int i=0; i<N-1; i++)
in[i] = false;
res_min = INT32_MAX;
res_max = INT32_MIN;
op_rec(0, numbers[0]);
cout<<res_max<<"\n"<<res_min;
}