728x90
반응형
4분기로 나누는 방법과 1분기로 가는 방법이 있다.
https://book.algospot.com/estimation.html
이것은 연산 개수 당 걸리는 시간에 대한 자료이니 참고하는 것이 좋다.
연산자 끼워넣기 문제에서, 10!로 1분기의 경우 1.3초가 걸렸다.
4분기는 O(4^n)으로 0ms가 걸렸다.
따라서 1분기도 가능하지만 4분기가 좋다.
연산자 끼워넣기(2) 문제는 1분기로 하게 되면, 44P10으로 연산량이 많아 시간초과가 난다.
따라서 4분기로 나누면 O(4^n)으로 0ms가 걸린다.
1분기
// 연산자 끼워넣기
#include <iostream>
#include <vector>
using namespace std;
char operatorArray[] = {'+', '-', '*', '/'};
vector<int> numVector;
bool selected[11] = {false};
long long maxNum = -9876543210;
long long minNum = 9876543210;
void permutation(int index,vector<char> realOperatorVector, vector<char> operatorVector){
if(index == realOperatorVector.size()){
long long sum = numVector[0];
for(int i = 1; i < numVector.size(); i++){
if(operatorVector[i - 1] == '+'){
sum += numVector[i];
}
else if(operatorVector[i - 1] == '-'){
sum -= numVector[i];
}
else if(operatorVector[i - 1] == '*'){
sum *= numVector[i];
}
else{
sum /= numVector[i];
}
}
if(maxNum < sum) maxNum = sum;
if(minNum > sum) minNum = sum;
return;
}
for(int i = 0; i < realOperatorVector.size(); i++){
if(selected[i]) continue;
selected[i] = true;
operatorVector.push_back(realOperatorVector[i]);
permutation(index + 1, realOperatorVector, operatorVector);
operatorVector.pop_back();
selected[i] = false;
}
}
int main(void){
int count, num, operatorCount;
vector<char> realOperatorVector, operatorVector;
cin >> count;
for(int i = 0; i < count; i++){
cin >> num;
numVector.push_back(num);
}
for(int i = 0; i < 4; i++){
cin >> operatorCount;
while(operatorCount--){
realOperatorVector.push_back(operatorArray[i]);
}
}
permutation(0, realOperatorVector, operatorVector);
cout << maxNum << "\n" << minNum;
}
4분기
// 연산자 끼워넣기(2)
#include <iostream>
#include <vector>
using namespace std;
vector<int> numVector;
bool selected[11] = {false};
long long maxNum = -9876543210;
long long minNum = 9876543210;
void permutation(int index, int size, int plusCount, int minusCount, int multipleCount, int divideCount, long long sum){
if(index == size){
maxNum = max(maxNum, sum);
minNum = min(minNum, sum);
return;
}
if(plusCount != 0) permutation(index + 1, size, plusCount - 1,minusCount, multipleCount, divideCount, sum + numVector[index + 1]);
if(minusCount != 0) permutation(index + 1, size, plusCount,minusCount - 1, multipleCount, divideCount, sum - numVector[index + 1]);
if(multipleCount != 0) permutation(index + 1, size, plusCount,minusCount, multipleCount - 1, divideCount, sum * numVector[index + 1]);
if(divideCount != 0) permutation(index + 1, size, plusCount,minusCount, multipleCount, divideCount - 1, sum / numVector[index + 1]);
}
int main(void){
vector<int> operatorVector;
int count, num;
cin >> count;
for(int i = 0; i < count; i++){
cin >> num;
numVector.push_back(num);
}
for(int i = 0; i < 4; i++){
cin >> num;
operatorVector.push_back(num);
}
permutation(0,count - 1,operatorVector[0],operatorVector[1],operatorVector[2],operatorVector[3], numVector[0]);
cout << maxNum << "\n" << minNum;
}
https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102906.cpp
https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102907.cpp
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 암호만들기 (0) | 2020.10.30 |
---|---|
[algorithm] 백준 - 퇴사 (0) | 2020.10.30 |
[algorithm] 백준 - 이모티콘 (0) | 2020.10.30 |
[algorithm] 백준 - N과 M(10) (0) | 2020.10.30 |
[algorithm] 백준 - N과 M(9) (0) | 2020.10.30 |