개요
https://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개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
접근 방식
-
문제를 제대로 못 봐서 삽질한 문제다...
"이때, 주어진 수의 순서를 바꾸면 안 된다." 이 문구를 그냥 지나쳐서,
수의 순서와 연산자 순서를 전부 백트래킹하도록 구현했더니 시간초과가 나와서 의아했다.예를들어 예제 3번같은 경우, 최대값이 70이 나왔다.
stack자료구조를 이용해 70찍혔을 때, 진행 순서를 봤다.
3 + 4 + 5 * 6 - 2 / 1을 해서 70이 나온 것이다.의아해서 다시 봤더니 순서를 바꾸면 안된다!!!
-
고친결과 코드가 매우 간결해져서 억울했다.
-
백트래킹처럼 재귀함수를 쓸 때 늘 주의할점은 역시나 함수를 빠져나왔을 때 값 초기화다.
예를 들어 주석처리한 부분 처럼case 1: //재귀함수에서 값 자체 건드려버리면 함수 빠져나오고 다시처리해야되서 그냥 함수넣어줄때 해주는게 편함 //prevResult -= elem; Backtracking(curStep + 1, false, prevResult - nums[curStep / 2], 0); break;prevResult-=elem을 하고 (elem은 nums[curStep/2]와 같은 변수다.) 함수를 호출하게 되면
함수 빠져나왔을 때 반드시 prevResult+=elem을 통해 원래대로 돌려놔야한다.+=연산자를 통해 안 돌려놓는다면 재귀를 빠져나와서 for문을 통해 다음 값을 처리할때
이전 재귀값인 prevResult값을 그대로 사용하게 되어 엉뚱하게 진행된다.이게 귀찮으면 내가 짠 방식처럼 함수 parameter에 prevResult - nums[curStep / 2]
값을 넣어주면 된다.
전체 코드
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int MaxNum=-1'000'000'000, MinNum=1'000'000'000,operandsSize;
int operandVisited[4];
//bool numVisited[12];
vector<int> nums;
//+ - * / 순서
vector<int> operands;
void Backtracking(int curStep, bool isNumTurn, int prevResult, int prevOperand) {
if (curStep == nums.size() + operandsSize) {
MaxNum = prevResult > MaxNum ? prevResult : MaxNum;
MinNum = prevResult > MinNum ? MinNum : prevResult;
return;
}
//숫자 차례라면
if (isNumTurn) {
//처음 순서면 연산필요없으므로 바로저장
if (curStep == 0) {
Backtracking(1, false, prevResult, 0);
return;
}
//처음 순서 아니라면
else
switch (prevOperand)
{
case 0:
Backtracking(curStep + 1, false, prevResult + nums[curStep / 2], 0);
break;
case 1:
//재귀함수에서 값 자체 건드려버리면 함수 빠져나오고 다시처리해야되서 그냥 함수넣어줄때 해주는게 편함
//prevResult -= elem;
Backtracking(curStep + 1, false, prevResult - nums[curStep / 2], 0);
break;
case 2:
Backtracking(curStep + 1, false, prevResult * nums[curStep / 2], 0);
break;
case 3:
Backtracking(curStep + 1, false, prevResult / nums[curStep / 2], 0);
break;
default:
break;
}
}
//연산자 차례라면
else
//4개의 연산자 중
for (int i = 0; i < 4; i++) {
if (operands[i] == 0) continue;
//방문한 횟수가 연산자 갯수보다 많다면 안됨
if (operandVisited[i] == operands[i]) continue;
operandVisited[i]++;
Backtracking(curStep + 1, true, prevResult, i);
//빠져나가면서 현재 사용한 operand초기화
operandVisited[i]--;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int amount, num, operand;
cin >> amount;
for (int i = 0; i < amount; i++) {
cin >> num;
nums.push_back(num);
}
for (int i = 0; i < 4; i++) {
cin >> operand;
operandsSize += operand;
operands.push_back(operand);
}
Backtracking(0, true, nums[0], 0);
cout << MaxNum << "\n";
cout << MinNum;
}문풀후생
min값은 10억을 설정했지만, max값은 0을 설정해서 처음에 틀렸었다.
max값도 -10억으로 설정해야한다..
