[백준] 14888 연산자 끼워넣기
문제
- N개의 수로 이루어진 수열 A1, A2, ..., AN과 N-1개의 연산자(덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷))
- 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행
- 만들 수 있는 식의 결과가 최대인 것과 최소
입력
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어짐
둘째 줄에는 A1, A2, ..., AN
셋째 줄에는 합이 N-1인 4개의 정수 (차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷))
출력
첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력
식의 결과는 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
풀이
수열을 앞에서부터 순서대로 진행하면서 넣을 수 있는 연산자의 모든 조합을 알아봐야함.
-> DFS로 풀이
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int N;
int oper[4] = { 0, }; //연산자 개수 저장
vector<int> nums; //수열 저장
int rmin = 1000000001; //최소값
int rmax = -1000000001; //최대값
void cal(int index, int result) {
if (index >= N) {
if (rmin > result) {
rmin = result; //최소값 갱신
}
if (rmax < result) {
rmax = result; //최대값 갱신
}
return;
}
for (int i = 0; i < 4; i++) {
if (oper[i] > 0) {
oper[i]--; //연산자가 존재하는 경우 -1
if (i == 0) { //더하기인 경우
cal(index+1, result+nums[index]);
}
else if (i == 1) { //빼기인 경우
cal(index + 1, result-nums[index]);
}
else if (i == 2) { //곱하기인 경우
cal(index + 1, result * nums[index]);
}
else { //나누기인 경우
cal(index + 1, result / nums[index]);
}
oper[i]++; //탐색 종료 후 +1 (원상복귀)
}
}
return;
}
int main() {
cin >> N;
int temp;
for (int i = 0; i < N; i++) {
cin >> temp;
nums.push_back(temp);
}
for (int i = 0; i < 4; i++) {
cin >> temp;
oper[i] = temp;
}
cal(1, nums[0]); //첫번째값 넣은 후 탐색 시작
cout << rmax << "\n";
cout << rmin << "\n";
return 0;
}
Author And Source
이 문제에 관하여([백준] 14888 연산자 끼워넣기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@botong_99/백준-14888-연산자끼워넣기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)