[삼성 14888] 연산자 끼워넣기
https://www.acmicpc.net/problem/14888
문제 설명
- N개의 순열
- N-1개의 연산자를 N개 순열 사이에 끼워넣었을 때 계산의 결과의 최댓값과 최솟값을 찾아라
- 연산자는 +,-,*,/ 순으로 몇개씩 있는지가 주어진다.
- 계산할 땐 우선순위 없이 앞에서부터 차례대로한다.
- 음수/양수 계산 시엔 양의 몫을 구해 음수화해준다.(나누는 수는 항상 양수이다.)
아이디어
N<11이므로 완전탐색이 가능하다고 생각했고, 재귀함수에서 현재까지 계산한 값을 받아서 4개의 연산자를 한번씩 덧붙여서 재귀하면 된다.
참고로 결과물(중간결과물 포함)이 다 10만(10^9)이하래서 int로 해결가능하다.
삽질
- 구현이 오래걸림^^... 처음에 연산자 4개 FOR문 돌려서 겹치는 과정 일반화 해줬는데(중간과정은 좀 다르게)
그게 마음에 안들어서 for없애고 걍 줄줄썼다가 다시 돌아옴^^^.. - 나눗셈 구현에서 음수/양수, 양수/양수 케이스를 반대로 구현해갖고 어디서 틀렸는지 몰라서 traker란 vector에다 결과물이 만들어준 연산자 순서를 저장해서 결과물이 나올 때 찍어봤다.
코드
https://www.acmicpc.net/source/23167877
#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
vector<int> nums;
int mmin=pow(10,9), mmax=-pow(10,9);//전체 결과중에서
int counter = 0;
void one_proc(int mom_res, int s, vector<int> yeons,vector<int> tracker) {//s는 연산자가 적용될 인덱스
counter++;
if (s == nums.size()) {
/*
cout << "계산결과 비교중" << mmin << " , " << mmax << " , " << mom_res << endl;
for (int i = 0; i < tracker.size(); i++) {
cout << tracker[i] << " ";
}
cout << endl;
*/
mmin = min(mmin, mom_res);
mmax = max(mmax, mom_res);
return;
}
for (int i = 0; i < 4; i++) {
int res = mom_res;
if (yeons[i] <= 0) {
continue;
}
yeons[i]--;
if (i == 0) {
res = res + nums[s];
}
else if (i == 1) {
res = res - nums[s];
}
else if (i == 2) {
res = res * nums[s];
}
else if (i == 3) {
if (res > 0) {
res = res / nums[s];
}
else {
res = -(abs(res) / nums[s]);
}
}
vector<int> temp_tracker = tracker;
temp_tracker.push_back(i);
/*
cout << "right before dfs" << endl;
for (int i = 0; i < temp_tracker.size(); i++) {
cout << temp_tracker[i] << " ";
}
cout << " == " << res << endl;
*/
one_proc(res, s + 1, yeons,temp_tracker);
yeons[i]++;//복구
}
}
int main() {
int n;
vector<int> yeons;//4가지 연산자의 개수
cin >> n;
int num;
for (int i = 0; i < n; i++) {
cin >> num;
nums.push_back(num);
}
for (int i = 0; i < 4; i++) {
cin >> num;
yeons.push_back(num);
}
vector<int> tracker;
one_proc(nums[0], 1, yeons,tracker);
cout << mmax << endl;
cout << mmin << endl;
}
Author And Source
이 문제에 관하여([삼성 14888] 연산자 끼워넣기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@coding3392/삼성-14888-연산자-끼워넣기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)